re PR libgomp/51249 (semaphore implemetation for linux leaves threads blocked)

	PR libgomp/51249
	* config/linux/sem.h: Rewrite.
	* config/linux/sem.c: Rewrite.

From-SVN: r181831

3 files changed, 94 insertions, 36 deletions

diff --git a/libgomp/ChangeLog b/libgomp/ChangeLog
index e248138..e9148f6 100644
--- a/libgomp/ChangeLog
+++ b/libgomp/ChangeLog
@@ -1,3 +1,9 @@
+2011-11-30  Alan Modra  <amodra@gmail.com>
+
+	PR libgomp/51249
+	* config/linux/sem.h: Rewrite.
+	* config/linux/sem.c: Rewrite.
+
 2011-11-28  Richard Henderson  <rth@redhat.com>
 
 	* libgomp.h (enum memmodel): New.
@@ -316,7 +322,7 @@
 	    Tobias Burnus  <burnus@net-b.de>
 
 	PR fortran/32049
-	* configure.ac: 
+	* configure.ac:
 	* configure: Regenerate.
 
 2010-10-06  Marcus Shawcroft  <marcus.shawcroft@arm.com>
@@ -1080,7 +1086,7 @@
 	(gomp_new_thread_pool, gomp_free_pool_helper, gomp_free_thread): New
 	functions.
 	(gomp_team_start): Create new pool if current thread doesn't have
-	one.  Use pool fields instead of global gomp_* variables. 
+	one.  Use pool fields instead of global gomp_* variables.
 	Initialize thread_pool field for new threads.  Clear single_count.
 	Change last argument from ws to team, don't create
 	new team, set ts.work_share to &team->work_shares[0] and clear
@@ -1312,7 +1318,7 @@
 	inlines.
 	* config/posix/bar.c (gomp_barrier_init): Clear generation field.
 	(gomp_barrier_wait_end): Change second argument to
-	gomp_barrier_state_t. 
+	gomp_barrier_state_t.
 	(gomp_team_barrier_wait, gomp_team_barrier_wait_end,
 	gomp_team_barrier_wake): New functions.
 	* config/linux/mutex.c: Include wait.h instead of libgomp.h and
diff --git a/libgomp/config/linux/sem.c b/libgomp/config/linux/sem.c
index ea98102..3f2fc99 100644
--- a/libgomp/config/linux/sem.c
+++ b/libgomp/config/linux/sem.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 2005, 2008, 2009 Free Software Foundation, Inc.
+/* Copyright (C) 2005, 2008, 2009, 2011 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU OpenMP Library (libgomp).
@@ -28,34 +28,56 @@
 
 #include "wait.h"
 
-
 void
-gomp_sem_wait_slow (gomp_sem_t *sem)
+gomp_sem_wait_slow (gomp_sem_t *sem, int count)
 {
+  /* First loop spins a while.  */
+  while (count == 0)
+    if (do_spin (sem, 0)
+	/* Spin timeout, nothing changed.  Set waiting flag.  */
+	&& __atomic_compare_exchange_n (sem, &count, SEM_WAIT, false,
+					MEMMODEL_ACQUIRE, MEMMODEL_RELAXED))
+      {
+	futex_wait (sem, SEM_WAIT);
+	count = *sem;
+	break;
+      }
+  /* Something changed.  If it wasn't the wait flag, we're good to go.  */
+    else if (__builtin_expect (((count = *sem) & SEM_WAIT) == 0 && count != 0,
+			       1))
+      {
+	if (__atomic_compare_exchange_n (sem, &count, count - SEM_INC, false,
+					 MEMMODEL_ACQUIRE, MEMMODEL_RELAXED))
+	  return;
+      }
+
+  /* Second loop waits until semaphore is posted.  We always exit this
+     loop with wait flag set, so next post will awaken a thread.  */
   while (1)
     {
-      int val = __sync_val_compare_and_swap (sem, 0, -1);
-      if (val > 0)
+      unsigned int wake = count & ~SEM_WAIT;
+      int newval = SEM_WAIT;
+
+      if (wake != 0)
+	newval |= wake - SEM_INC;
+      if (__atomic_compare_exchange_n (sem, &count, newval, false,
+				       MEMMODEL_ACQUIRE, MEMMODEL_RELAXED))
 	{
-	  if (__sync_bool_compare_and_swap (sem, val, val - 1))
-	    return;
+	  if (wake != 0)
+	    {
+	      /* If we can wake more threads, do so now.  */
+	      if (wake > SEM_INC)
+		gomp_sem_post_slow (sem);
+	      break;
+	    }
+	  do_wait (sem, SEM_WAIT);
+	  count = *sem;
 	}
-      do_wait (sem, -1);
     }
 }
 
 void
 gomp_sem_post_slow (gomp_sem_t *sem)
 {
-  int old, tmp = *sem, wake;
-
-  do
-    {
-      old = tmp;
-      wake = old > 0 ? old + 1 : 1;
-      tmp = __sync_val_compare_and_swap (sem, old, wake);
-    }
-  while (old != tmp);
-
-  futex_wake (sem, wake);
+  futex_wake (sem, 1);
 }
diff --git a/libgomp/config/linux/sem.h b/libgomp/config/linux/sem.h
index 9b0f0f8..9bf480d 100644
--- a/libgomp/config/linux/sem.h
+++ b/libgomp/config/linux/sem.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2005, 2009 Free Software Foundation, Inc.
+/* Copyright (C) 2005, 2009, 2011 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU OpenMP Library (libgomp).
@@ -24,34 +24,64 @@
 
 /* This is a Linux specific implementation of a semaphore synchronization
    mechanism for libgomp.  This type is private to the library.  This 
-   implementation uses atomic instructions and the futex syscall.  */
+   counting semaphore implementation uses atomic instructions and the
+   futex syscall, and a single 32-bit int to store semaphore state.
+   The low 31 bits are the count, the top bit is a flag set when some
+   threads may be waiting.  */
 
 #ifndef GOMP_SEM_H
 #define GOMP_SEM_H 1
 
+#include <limits.h> /* For INT_MIN */
+
 typedef int gomp_sem_t;
+#define SEM_WAIT INT_MIN
+#define SEM_INC 1
+
+extern void gomp_sem_wait_slow (gomp_sem_t *, int);
+extern void gomp_sem_post_slow (gomp_sem_t *);
 
-static inline void gomp_sem_init (gomp_sem_t *sem, int value)
+static inline void
+gomp_sem_init (gomp_sem_t *sem, int value)
 {
-  *sem = value;
+  *sem = value * SEM_INC;
 }
 
-extern void gomp_sem_wait_slow (gomp_sem_t *);
-static inline void gomp_sem_wait (gomp_sem_t *sem)
+static inline void
+gomp_sem_destroy (gomp_sem_t *sem)
 {
-  if (!__sync_bool_compare_and_swap (sem, 1, 0))
-    gomp_sem_wait_slow (sem);
 }
 
-extern void gomp_sem_post_slow (gomp_sem_t *);
-static inline void gomp_sem_post (gomp_sem_t *sem)
+static inline void
+gomp_sem_wait (gomp_sem_t *sem)
 {
-  if (!__sync_bool_compare_and_swap (sem, 0, 1))
-    gomp_sem_post_slow (sem);
+  int count = *sem;
+
+  while ((count & ~SEM_WAIT) != 0)
+    if (__atomic_compare_exchange_n (sem, &count, count - SEM_INC, true,
+				     MEMMODEL_ACQUIRE, MEMMODEL_RELAXED))
+      return;
+  gomp_sem_wait_slow (sem, count);
 }
 
-static inline void gomp_sem_destroy (gomp_sem_t *sem)
+static inline void
+gomp_sem_post (gomp_sem_t *sem)
 {
-}
+  int count = *sem;
+
+  /* Clear SEM_WAIT here so that if there are no more waiting threads
+     we transition back to the uncontended state that does not make
+     futex syscalls.  If there are waiting threads then when one is
+     awoken it will set SEM_WAIT again, so other waiting threads are
+     woken on a future gomp_sem_post.  Furthermore, the awoken thread
+     will wake other threads in case gomp_sem_post was called again
+     before it had time to set SEM_WAIT.  */
+  while (!__atomic_compare_exchange_n (sem, &count,
+				       (count + SEM_INC) & ~SEM_WAIT, true,
+				       MEMMODEL_RELEASE, MEMMODEL_RELAXED))
+    continue;
 
+  if (__builtin_expect (count & SEM_WAIT, 0))
+    gomp_sem_post_slow (sem);
+}
 #endif /* GOMP_SEM_H */