ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Doug Kwan (關振德)]

[-- Attachment #1: Type: text/plain, Size: 596 bytes --]

Hi,

    I have sent this out in June.  Could someone please review this?
This patch fixes a deadlock problem in function scope static variable.
The current code there uses a big mutex for locking everything and the
mutex is acquired throughout the whole time a variable is being
initialized.  If the initalization code spawns and waits for another
another thread which needs to initialize another static variable, a
deadlock will result.  My fix is to use a bit per object for locking.
The bit is only accessed when the global mutex is acquired.  The mutex
is held only briefly.

Thanks.

-Doug

[-- Attachment #2: ChangeLog-gcc --]
[-- Type: application/octet-stream, Size: 1650 bytes --]

2007-06-08  Doug Kwan  <dougkwan@google.com>

	* gthr-posix.h (__gthread_cond_broadcast, __gthread_cond_wait,
	__gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
	Add to extend interface for POSIX conditional variables.
	(__GTHREAD_HAS_COND): Macro defined to signify support of
	conditional variables.
	* gthr-single.h (__gthread_cond_broadcast, __gthread_cond_wait,
	__gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
	Add to extend interface for POSIX conditional variables.
	* gthr.h: Update comments to document new interface.

	* include/ext/concurrent.h (class __mutex, class __recursive_mutex):
	Add new method gthread_mutex to access inner gthread mutex. 
	[__GTHREAD_HAS_COND] (class __concurrence_broadcast_error,
	class __concurrence_wait_error, class __cond): Add.
	* libsup++/guard.cc (random_level, new_skip_list_node,
	skip_list_search_internal, new_skip_list, skip_list_insert_key,
	skip_list_delete_key, skip_list_search_key). Add to implement skip
	list to map guard variables and thread ID's.
	(recurisve_push, recursive_pop): Delete.
	(init_in_progress_flag, set_init_in_progress_flag): Add to
	replace recursive_push and recursive_pop.
	(throw_recursive_init_exception): Add.
	(acquire, __cxa_guard_acquire, __cxa_guard_abort and
	__cxa_guard_release): [__GTHREAD_HAS_COND] Use a conditional
	for synchronization of static variable initialization.
	The global mutex is only held briefly when guards are
	accessed. [!__GTHREAD_HAS_COND] Fall back to the old code,
	which deadlocks.
	* testsuite/thread/guard.cc: Add new test. It deadlocks with the
	old locking code in libstdc++-v3/libsup++/guard.cc.

[-- Attachment #3: diffs-2007.06.18 --]
[-- Type: application/octet-stream, Size: 27614 bytes --]

diff -Nru ../gcc-4.2.0/gcc-4.2.0/gcc/gthr-posix.h gcc-4.2.0/gcc/gthr-posix.h
--- ../gcc-4.2.0/gcc-4.2.0/gcc/gthr-posix.h	2006-12-12 07:21:53.000000000 -0800
+++ gcc-4.2.0/gcc/gthr-posix.h	2007-06-06 17:19:43.468669000 -0700
@@ -43,10 +43,16 @@
 #include <pthread.h>
 #include <unistd.h>
 
+typedef pthread_t __gthread_t;
 typedef pthread_key_t __gthread_key_t;
 typedef pthread_once_t __gthread_once_t;
 typedef pthread_mutex_t __gthread_mutex_t;
 typedef pthread_mutex_t __gthread_recursive_mutex_t;
+typedef pthread_cond_t __gthread_cond_t;
+
+/* POSIX like conditional variables are supported.  Please look at comments
+   in gthr.h for details. */
+#define __GTHREAD_HAS_COND	1	
 
 #define __GTHREAD_MUTEX_INIT PTHREAD_MUTEX_INITIALIZER
 #define __GTHREAD_ONCE_INIT PTHREAD_ONCE_INIT
@@ -57,6 +63,7 @@
 #else
 #define __GTHREAD_RECURSIVE_MUTEX_INIT_FUNCTION __gthread_recursive_mutex_init_function
 #endif
+#define __GTHREAD_COND_INIT PTHREAD_COND_INITIALIZER
 
 #if SUPPORTS_WEAK && GTHREAD_USE_WEAK
 # define __gthrw2(name,name2,type) \
@@ -84,6 +91,9 @@
 __gthrw3(pthread_mutex_trylock)
 __gthrw3(pthread_mutex_unlock)
 __gthrw3(pthread_mutex_init)
+__gthrw3(pthread_cond_broadcast)
+__gthrw3(pthread_cond_wait)
+__gthrw3(pthread_self)
 #else
 __gthrw(pthread_once)
 __gthrw(pthread_getspecific)
@@ -94,6 +104,9 @@
 __gthrw(pthread_mutex_trylock)
 __gthrw(pthread_mutex_unlock)
 __gthrw(pthread_mutex_init)
+__gthrw(pthread_cond_broadcast)
+__gthrw(pthread_cond_wait)
+__gthrw(pthread_self)
 #endif
 
 __gthrw(pthread_key_create)
@@ -101,28 +114,22 @@
 __gthrw(pthread_mutexattr_init)
 __gthrw(pthread_mutexattr_settype)
 __gthrw(pthread_mutexattr_destroy)
-
+__gthrw(pthread_equal)
 
 #if defined(_LIBOBJC) || defined(_LIBOBJC_WEAK)
 /* Objective-C.  */
 #if defined(__osf__) && defined(_PTHREAD_USE_MANGLED_NAMES_)
-__gthrw3(pthread_cond_broadcast)
 __gthrw3(pthread_cond_destroy)
 __gthrw3(pthread_cond_init)
 __gthrw3(pthread_cond_signal)
-__gthrw3(pthread_cond_wait)
 __gthrw3(pthread_exit)
 __gthrw3(pthread_mutex_destroy)
-__gthrw3(pthread_self)
 #else
-__gthrw(pthread_cond_broadcast)
 __gthrw(pthread_cond_destroy)
 __gthrw(pthread_cond_init)
 __gthrw(pthread_cond_signal)
-__gthrw(pthread_cond_wait)
 __gthrw(pthread_exit)
 __gthrw(pthread_mutex_destroy)
-__gthrw(pthread_self)
 #endif /* __osf__ && _PTHREAD_USE_MANGLED_NAMES_ */
 #ifdef _POSIX_PRIORITY_SCHEDULING
 #ifdef _POSIX_THREAD_PRIORITY_SCHEDULING
@@ -664,6 +671,37 @@
   return __gthread_mutex_unlock (mutex);
 }
 
+static inline int
+__gthread_cond_broadcast (__gthread_cond_t *cond)
+{
+  return __gthrw_(pthread_cond_broadcast) (cond);
+}
+
+static inline int
+__gthread_cond_wait (__gthread_cond_t *cond, __gthread_mutex_t *mutex)
+{
+  return __gthrw_(pthread_cond_wait) (cond, mutex);
+}
+
+static inline int
+__gthread_cond_wait_recursive (__gthread_cond_t *cond,
+			       __gthread_recursive_mutex_t *mutex)
+{
+  return __gthread_cond_wait (cond, mutex);
+}
+
+static inline __gthread_t
+__gthread_self (void)
+{
+  return __gthrw_(pthread_self) ();
+}
+
+static inline int
+__gthread_equal (__gthread_t t1, __gthread_t t2)
+{
+  return __gthrw_(pthread_equal) (t1, t2);
+}
+
 #endif /* _LIBOBJC */
 
 #endif /* ! GCC_GTHR_POSIX_H */
diff -Nru ../gcc-4.2.0/gcc-4.2.0/gcc/gthr-single.h gcc-4.2.0/gcc/gthr-single.h
--- ../gcc-4.2.0/gcc-4.2.0/gcc/gthr-single.h	2005-06-24 19:02:01.000000000 -0700
+++ gcc-4.2.0/gcc/gthr-single.h	2007-05-22 15:38:28.663135000 -0700
@@ -251,6 +251,37 @@
   return __gthread_mutex_unlock (mutex);
 }
 
+static inline int
+__gthread_cond_broadcast (__gthread_cond_t cond)
+{
+  return 0;
+}
+
+static inline int
+__gthread_cond_wait (__gthread_cond_t cond, __gthread_mutex_t *mutex)
+{
+  return 0;
+}
+
+static inline int
+__gthread_cond_wait_recursive (__gthread_cond_t cond,
+			       __gthread_recursive_mutex_t *mutex)
+{
+  return 0;
+}
+
+static inline __gthread_t
+__gthread_self (void)
+{
+  return (__gthread_t)0;
+}
+
+static inline int
+__gthread_equal (__gthread_t t1, __gthread_t t2)
+{
+  return (t1 == t2);
+}
+
 #endif /* _LIBOBJC */
 
 #undef UNUSED
diff -Nru ../gcc-4.2.0/gcc-4.2.0/gcc/gthr.h gcc-4.2.0/gcc/gthr.h
--- ../gcc-4.2.0/gcc-4.2.0/gcc/gthr.h	2005-06-24 19:02:01.000000000 -0700
+++ gcc-4.2.0/gcc/gthr.h	2007-05-29 15:27:10.629612000 -0700
@@ -81,6 +81,27 @@
      int __gthread_recursive_mutex_trylock (__gthread_recursive_mutex_t *mutex);
      int __gthread_recursive_mutex_unlock (__gthread_recursive_mutex_t *mutex);
 
+   The following are supported in POSIX threads only. They are required to
+   fix a deadlock in static initialization inside libsupc++. The header file
+   gthr-posix.h defines a symbol __GTHREAD_HAS_COND to signify that these extra
+   features are supported.
+
+   Types:
+     __gthread_t
+     __gthread_cond_t
+
+   Macros:
+     __GTHREAD_COND_INIT
+     __GTHREAD_COND_INIT_FUNCTION
+
+   Interface:
+     int __gthread_cond_broadcast (__gthread_cond_t *cond);
+     int __gthread_cond_wait (__gthread_cond_t *cond, __gthread_mutex_t *mutex);
+     int __gthread_cond_wait_recursive (__gthread_cond_t *cond,
+					__gthread_recursive_mutex_t *mutex);
+     __gthread_t __gthread_self (void);
+     int __gthread_equal (__gthread_t t1, __gthread_t t2);
+
    All functions returning int should return zero on success or the error
    number.  If the operation is not supported, -1 is returned.
 
diff -Nru ../gcc-4.2.0/gcc-4.2.0/libstdc++-v3/include/ext/concurrence.h gcc-4.2.0/libstdc++-v3/include/ext/concurrence.h
--- ../gcc-4.2.0/gcc-4.2.0/libstdc++-v3/include/ext/concurrence.h	2006-11-13 01:18:24.000000000 -0800
+++ gcc-4.2.0/libstdc++-v3/include/ext/concurrence.h	2007-06-15 16:51:50.728412000 -0700
@@ -83,6 +83,22 @@
     { return "__gnu_cxx::__concurrence_unlock_error"; }
   };
 
+  class __concurrence_broadcast_error : public std::exception
+  {
+  public:
+    virtual char const*
+    what() const throw()
+    { return "__gnu_cxx::__concurrence_broadcast_error"; }
+  };
+
+  class __concurrence_wait_error : public std::exception
+  {
+  public:
+    virtual char const*
+    what() const throw()
+    { return "__gnu_cxx::__concurrence_wait_error"; }
+  };
+
   // Substitute for concurrence_error object in the case of -fno-exceptions.
   inline void
   __throw_concurrence_lock_error()
@@ -104,6 +120,28 @@
 #endif
   }
 
+#ifdef __GTHREAD_HAS_COND
+  inline void
+  __throw_concurrence_broadcast_error()
+  {
+#if __EXCEPTIONS
+    throw __concurrence_broadcast_error();
+#else
+    __builtin_abort();
+#endif
+  }
+
+  inline void
+  __throw_concurrence_wait_error()
+  {
+#if __EXCEPTIONS
+    throw __concurrence_wait_error();
+#else
+    __builtin_abort();
+#endif
+  }
+#endif
+ 
   class __mutex 
   {
   private:
@@ -149,6 +187,9 @@
 	}
 #endif
     }
+
+    __gthread_mutex_t* gthread_mutex(void)
+      { return &_M_mutex; }
   };
 
   class __recursive_mutex 
@@ -196,6 +237,9 @@
 	}
 #endif
     }
+
+    __gthread_recursive_mutex_t* gthread_recursive_mutex(void)
+      { return &_M_mutex; }
   };
 
   /// @brief  Scoped lock idiom.
@@ -220,6 +264,66 @@
     { _M_device.unlock(); }
   };
 
+#ifdef __GTHREAD_HAS_COND
+  class __cond
+  {
+  private:
+    __gthread_cond_t _M_cond;
+
+    __cond(const __cond&);
+    __cond& operator=(const __cond&);
+
+  public:
+    __cond() 
+    { 
+#if __GTHREADS
+      if (__gthread_active_p())
+	{
+#if defined __GTHREAD_COND_INIT
+	  __gthread_cond_t __tmp = __GTHREAD_COND_INIT;
+	  _M_cond = __tmp;
+#else
+	  __GTHREAD_MUTEX_INIT_FUNCTION(&_M_cond);
+#endif
+	}
+#endif 
+    }
+
+    void broadcast()
+    {
+#if __GTHREADS
+      if (__gthread_active_p())
+	{
+	  if (__gthread_cond_broadcast(&_M_cond) != 0)
+	    __throw_concurrence_broadcast_error();
+	}
+#endif
+    }
+
+    void wait(__mutex *mutex)
+    {
+#if __GTHREADS
+      {
+	  if (__gthread_cond_wait(&_M_cond, mutex->gthread_mutex()) != 0)
+	    __throw_concurrence_wait_error();
+      }
+#endif
+    }
+
+    void wait_recursive(__recursive_mutex *mutex)
+    {
+#if __GTHREADS
+      {
+	  if (__gthread_cond_wait_recursive(&_M_cond,
+					    mutex->gthread_recursive_mutex())
+	      != 0)
+	    __throw_concurrence_wait_error();
+      }
+#endif
+    }
+  };
+#endif
+
 _GLIBCXX_END_NAMESPACE
 
 #endif
diff -Nru ../gcc-4.2.0/gcc-4.2.0/libstdc++-v3/libsupc++/guard.cc gcc-4.2.0/libstdc++-v3/libsupc++/guard.cc
--- ../gcc-4.2.0/gcc-4.2.0/libstdc++-v3/libsupc++/guard.cc	2006-10-11 13:18:36.000000000 -0700
+++ gcc-4.2.0/libstdc++-v3/libsupc++/guard.cc	2007-06-15 17:11:20.569819000 -0700
@@ -36,6 +36,20 @@
 #include <ext/atomicity.h>
 #include <ext/concurrence.h>
 
+#ifdef __GTHREADS
+#include <cstdlib>
+#if _GLIBCXX_HOSTED
+using std::free;
+using std::calloc;
+#else
+// In a freestanding environment, these functions may not be available
+// -- but for now, we assume that they are.
+extern "C" void *calloc(std::size_t, std::size_t);
+extern "C" void free(void *);
+extern "C" int rand_r(unsigned int *);
+#endif
+#endif
+
 // The IA64/generic ABI uses the first byte of the guard variable.
 // The ARM EABI uses the least significant bit.
 
@@ -62,6 +76,307 @@
   }
 }
 
+namespace
+{
+  // A single conditional variable controlling all static initializations.
+  static __gnu_cxx::__cond* static_cond;  
+
+  // using a fake type to avoid initializing a static class.
+  typedef char fake_cond_t[sizeof(__gnu_cxx::__cond)]
+  __attribute__ ((aligned(__alignof__(__gnu_cxx::__cond))));
+  fake_cond_t fake_cond;
+
+  static void init_static_cond()
+  { static_cond =  new (&fake_cond) __gnu_cxx::__cond(); }
+
+  __gnu_cxx::__cond&
+  get_static_cond()
+  {
+    static __gthread_once_t once = __GTHREAD_ONCE_INIT;
+    __gthread_once(&once, init_static_cond);
+    return *static_cond;
+  }
+}
+
+//
+// According to the Wikipedia:
+// 
+//   Invented in 1990 by William Pugh, a skip list is a probabilistic data
+//   structure, based on parallel linked lists, with efficiency comparable to
+//   a binary search tree (order O(log n)) average time for most operations.
+// 
+// When multithreading is enabled in run-time, we use a skip list to map
+// guard variables and threads currently initializing guarded variables. We
+// maintain this invariant:
+//
+// 	If a the guarded variable of a guard G is currently being initialized
+// 	by a thread P, the skip list contains an entry whose key is the address of
+// 	G and value P.
+//
+// To avoid a data race, the skip list is only accessed while a thread has
+// acquired the global mutex.
+//
+// References:
+// - Pugh, William (June 1990). "Skip lists: a probabilistic alternative to
+//   balanced trees". CACM 33:668-676
+// - http://en.wikipedia.org/wiki/Skip_list
+// 
+namespace
+{
+  // Seed for rand_r().
+  static unsigned int skip_list_rand_seed = 1;
+
+  typedef void* skip_list_key_t;
+  typedef __gthread_t skip_list_value_t;
+
+  // Since a node has variable number of forward pointers depending on its
+  // level, the skip_list_node_t below is really the header of a node. When a
+  // node is allocated, extra memory is allocated after the node for the
+  // forward pointers.
+  typedef struct skip_list_node_s
+  {
+    skip_list_key_t	key;
+    skip_list_value_t	value;
+    int			level;
+    struct skip_list_node_s*	forward[0];
+  } skip_list_node_t;
+
+  // A skip list consists of the struct below and a special head node, which
+  // has max_level + 1 slots and no key value. The head node is part of the
+  // list and is present even if the list is empty.
+  typedef struct skip_list_struct_s
+  {
+    skip_list_node_t*	head;
+    int			max_level;
+  } skip_list_t;
+
+// MAX_LEVEL_LIMIT is bigger than the maximum allowable max-level. This
+// corresponds to up to 4G nodes with O(log n) expected access time.
+#define MAX_LEVEL_LIMIT		32
+
+// DEFAULT_MAX_LEVEL handles up to 1 million nodes with O(log n) expected
+// access time.
+#define DEFAULT_MAX_LEVEL	19
+
+  // This returns a random number between 0 and max_level with an exponential
+  // distribution.
+  static int
+  random_level(int max_level)
+  {
+    int level=0;
+
+    while (level < max_level)
+      {
+	if (rand_r(&skip_list_rand_seed) < RAND_MAX/2)
+          break;
+	level++;
+      }
+
+    return level;
+  }
+
+  static skip_list_node_t*
+  new_skip_list_node(int level)
+  {
+    skip_list_node_t* new_node;
+    size_t node_size;
+
+    // Since we count levels from zero, allocate level + 1 slots after the
+    // node struct.
+    node_size = (sizeof(skip_list_node_t)
+		 + sizeof(skip_list_node_t*) * (level + 1));
+
+    new_node = (skip_list_node_t*) calloc(1, node_size);
+    if (!new_node)
+      throw std::bad_alloc();
+
+    new_node->level = level;
+    return new_node; 
+  }
+
+  // This is the internal search function shared by skip_list_insert_key() and
+  // skip_list_delete_key(). If it finds a node with the given key, it returns
+  // a pointer to the node. Otherwise it returns NULL. The update vector is set
+  // up for insertion and deletion. We only look at level at or below that of
+  // the list head. So update vector elements [head->level+1 ..
+  // MAX_LEVEL_LIMIT-1] are undefined.
+  static skip_list_node_t*
+  skip_list_search_internal(skip_list_t *list, skip_list_key_t key,
+			    skip_list_node_t *update[MAX_LEVEL_LIMIT])
+  {
+    int level;
+    skip_list_node_t* cursor;
+    skip_list_node_t* next;
+
+    cursor = list->head;
+    level = cursor->level;
+
+    // For all levels, find the node that is just before the position where
+    // a node with the given key would be.
+    while (level >= 0)
+      {
+	while (((next = cursor->forward[level]) != NULL) && (next->key < key))
+	  cursor = next;
+	update[level] = cursor;
+	level --;
+      } 
+
+    // If we find the node, cursor->forward[0] should point to it.
+    if (((next = cursor->forward[0]) != NULL) && next->key == key)
+      return next;
+    else
+      return NULL;
+  }
+
+  // Create a skip list with the maximum level being max_level. If max_level is
+  // outside the range [0..MAX_LEVEL_LIMIT), a default value will be used.
+  skip_list_t*
+  new_skip_list(int max_level)
+  {
+    skip_list_t* new_list;
+   
+    if (max_level < 0 || max_level >= MAX_LEVEL_LIMIT)
+      max_level = DEFAULT_MAX_LEVEL;
+
+    new_list = (skip_list_t*) calloc(1, sizeof(skip_list_t));
+    if (!new_list)
+      throw std::bad_alloc();
+    new_list->max_level = max_level; 
+
+    // The head is special. Its level changes over-time. So we allocate storage
+    // for the maximum level first even though its level is 0 initially.
+    new_list->head = new_skip_list_node(max_level);
+    new_list->head->level = 0;
+    return new_list;
+  }
+
+  // Insert a value with a key. If there is another value in the list with the
+  // same key, the old value with be replaced by the new one. In other words,
+  // a given key value can appear at most once in a skip list. If there is not
+  // enough memory to for insert to work. The result is undefined.
+  void
+  skip_list_insert_key(skip_list_t *list, skip_list_key_t key,
+		       skip_list_value_t value)
+  {
+    skip_list_node_t* node;
+    skip_list_node_t* update[MAX_LEVEL_LIMIT];
+    int level;
+
+    node = skip_list_search_internal(list, key, update);
+
+    // Create and insert a new node if necessary.
+    if (node == NULL)
+      {
+	level = random_level(list->max_level);
+	node = new_skip_list_node(level);
+	node->key = key;
+
+        // If the new node's level is higher than that of the head, bump up
+        // head level and fix the update vector.
+	if (level > list->head->level)
+	  { 
+	    while (level > list->head->level)
+	      {
+		update[level] = list->head;
+		level--;
+	      }
+	    list->head->level = node->level;
+	  }
+
+	for (level = node->level; level >= 0; level--)
+	  {
+	    node->forward[level] = update[level]->forward[level];
+	    update[level]->forward[level] = node;
+	  }
+      }
+
+    node->value = value;
+  }
+
+  // Remove the node in with the given key if such there is one.
+  // delete_skip_list() returns a non-zero value if and only if it there is a
+  // node with the given key in the skip list.
+  int
+  skip_list_delete_key(skip_list_t *list, skip_list_key_t key)
+  {
+    skip_list_node_t* node;
+    skip_list_node_t* head;
+    skip_list_node_t* update[MAX_LEVEL_LIMIT];
+    int level;
+
+    node = skip_list_search_internal(list, key, update);
+    if (node != NULL)
+      {
+	for (level = node->level; level >= 0; level --)
+	  update[level]->forward[level] = node->forward[level];
+
+	// We may need to reduce head level.
+	if (node->level == list->head->level)
+	  {
+	    head = list->head;
+	    level = head->level;
+	    while ((level > 0) && (head->forward[level] == NULL))
+	      level--;
+	    head->level = level;
+	  }
+	free(node);
+	return 1;
+      }
+    else 
+      return 0;
+  }
+
+  // Search the skip list for a value with the given key. If there is one, the
+  // result is stored in to the location pointed to by 'value_ptr' and
+  // skip_list_search_key() returns a non-zero value. If the key is not found
+  // in the skip list, skip_list_search_key() returns 0 and the value in the
+  // location pointed to by 'value_ptr' is undefined.
+  int
+  skip_list_search_key(skip_list_t *list, skip_list_key_t key,
+		       skip_list_value_t *value_ptr)
+  {
+    skip_list_node_t* cursor;
+    skip_list_node_t* next;
+    int level;
+
+    cursor = list->head;
+    level = cursor->level;
+
+    // The code below is similar to code in search_skip_list_internal() except
+    // we don't care about the update vector. So we simplify the code here for
+    // speed.
+    while (level >= 0)
+      {
+	while (((next = cursor->forward[level]) != NULL) && (next->key < key))
+	  cursor = next;
+
+	if ((next != NULL) && (next->key == key))
+	  {
+	    *value_ptr = next->value;
+	    return 1;
+	  }
+	else
+	  level--;
+      }
+
+    return 0;
+  }
+
+  // A single skip list is used to store thread ID's.
+  static skip_list_t* static_skip_list;
+
+  static void init_static_skip_list()
+  { static_skip_list = new_skip_list(DEFAULT_MAX_LEVEL); }
+
+  skip_list_t*
+  get_static_skip_list()
+  {
+    static __gthread_once_t once = __GTHREAD_ONCE_INIT;
+    __gthread_once(&once, init_static_skip_list);
+    return static_skip_list;
+  }
+}
+
 #ifndef _GLIBCXX_GUARD_TEST_AND_ACQUIRE
 inline bool
 __test_and_acquire (__cxxabiv1::__guard *g)
@@ -110,34 +425,87 @@
   recursive_init_error::~recursive_init_error() throw() { }
 }
 
+//
+// Here are C++ run-time routines for guarded initiailization of static
+// variables. There are 4 scenarios under which these routines are called:
+//
+//   1. Threads not supported (__GTHREADS not defined)
+//   2. Threads are supported but not enabled at run-time.
+//   3. Threads enabled at run-time but __gthreads_* are not fully POSIX.
+//   4. Threads enabled at run-time and __gthreads_* support all POSIX threads
+//      primitives we need here.
+//
+// The old code supported scenarios 1-3 but was broken since it used a global
+// mutex for all threads and had the mutex locked during the whole duration of
+// initlization of a guarded static variable. The following created a dead-lock
+// with the old code.
+//
+//	Thread 1 acquires the global mutex.
+//	Thread 1 starts initializing static variable.
+//	Thread 1 creates thread 2 during initialization.
+//	Thread 2 attempts to acuqire mutex to initialize another variable.
+//	Thread 2 blocks since thread 1 is locking the mutex.
+//	Thread 1 waits for result from thread 2 and also blocks. A deadlock.
+//
+// The new code here can handle this situation and thus is more robust. Howere,
+// we need to use the POSIX thread conditional variable, which is not supported
+// in all platforms, notably older versions of Microsoft Windows. The gthr*.h
+// headers define a symbol __GTHREAD_HAS_COND for platforms that support POSIX
+// like conditional variables. For platforms that do not support conditional
+// variables, we need to fall back to the old code.
 namespace __cxxabiv1 
 {
   static inline int
-  recursion_push (__guard* g)
-  { return ((char *)g)[1]++; }
+  init_in_progress_flag(__guard* g)
+  { return ((char *)g)[1]; }
 
   static inline void
-  recursion_pop (__guard* g)
-  { --((char *)g)[1]; }
+  set_init_in_progress_flag(__guard* g, int v)
+  { ((char *)g)[1] = v; }
 
-  static int
-  acquire (__guard *g)
+  static inline void
+  throw_recursive_init_exception()
   {
-    if (_GLIBCXX_GUARD_TEST (g))
-      return 0;
-
-    if (recursion_push (g))
-      {
 #ifdef __EXCEPTIONS
 	throw __gnu_cxx::recursive_init_error();
 #else
 	// Use __builtin_trap so we don't require abort().
-	__builtin_trap ();
+	__builtin_trap();
 #endif
-      }
+  }
+
+  // acuire() is a helper function used to acquire guard if thread support is
+  // not compiled in or is compiled in but not enabled at run-time.
+  static int
+  acquire(__guard *g)
+  {
+    // Quit if the object is already initialized.
+    if (_GLIBCXX_GUARD_TEST(g))
+      return 0;
+
+    if (init_in_progress_flag(g))
+	throw_recursive_init_exception();
+
+    set_init_in_progress_flag(g, 1);
     return 1;
   }
 
+  // Simple wrapper for exception safety.
+  struct mutex_wrapper
+  {
+#ifdef __GTHREADS
+    bool unlock;
+    mutex_wrapper() : unlock(true)
+    { get_static_mutex().lock(); }
+
+    ~mutex_wrapper()
+    {
+      if (unlock)
+	static_mutex->unlock();
+    }
+#endif
+  };
+
   extern "C"
   int __cxa_guard_acquire (__guard *g) 
   {
@@ -150,28 +518,56 @@
 
     if (__gthread_active_p ())
       {
-	// Simple wrapper for exception safety.
-	struct mutex_wrapper
-	{
-	  bool unlock;
-	  mutex_wrapper() : unlock(true)
-	  { get_static_mutex().lock(); }
+	mutex_wrapper mw;
 
-	  ~mutex_wrapper()
+	while (1)	// When this loop is executing, mutex is locked.
 	  {
-	    if (unlock)
-	      static_mutex->unlock();
-	  }
-	};
+#ifdef __GTHREAD_HAS_COND
+	    // This is similar to the logic in acquire() except that we need
+	    // to handle thread ID's. 
+	    
+	    // The static is allready initialized.
+	    if (_GLIBCXX_GUARD_TEST(g))
+	      return 0;	// The mutex will be unlocked via wrapper
+
+	    // Unlike acquire(), we need to examine thread ID's to determine
+	    // what action to take.
+	    __gthread_t id = __gthread_self();
+	    if (init_in_progress_flag(g))
+	      {
+		__gthread_t id2;
+
+		// The guarded static is currently being initialized. we
+		// need	check to see if it is done by the same thread.
+		skip_list_search_key(get_static_skip_list(), g, &id2);
+		if (__gthread_equal(id, id2))
+		  throw_recursive_init_exception();
+
+		// The guarded static is currently being initialized by
+		// another thread, so we release mutex and wait for the
+		// conditional variable. We will lock the mutex again after
+		// this.
+		get_static_cond().wait_recursive(&get_static_mutex());
+	      }
+	    else
+	      {
+		// We need to maintain the skip list invariant.
+		set_init_in_progress_flag(g, 1);
+		skip_list_insert_key(get_static_skip_list(), g, id);
 
-	mutex_wrapper mw;
-	if (acquire (g))
-	  {
-	    mw.unlock = false;
-	    return 1;
+		return 1; // The mutex will be unlocked via wrapper.
+	      }
+#else
+	    // This provides compatibility with older systems not supporting
+	    // POSIX like conditional variables.
+	    if (acquire(g))
+	      {
+		mw.unlock = false;
+		return 1; // The mutex still locked.
+	      }
+	    return 0; // The mutex will be unlocked via wrapper.
+#endif
 	  }
-
-	return 0;
       }
 #endif
 
@@ -181,8 +577,26 @@
   extern "C"
   void __cxa_guard_abort (__guard *g)
   {
-    recursion_pop (g);
-#ifdef __GTHREADS
+#ifdef __GTHREAD_HAS_COND
+    if (__gthread_active_p())
+      {	
+	mutex_wrapper mw;
+
+	// We need to maintain the skip list invariant.
+	set_init_in_progress_flag(g, 0);
+	skip_list_delete_key(get_static_skip_list(), g);
+
+	// If we abort, we still need to wake up all other threads waiting for
+	// the conditional variable.
+        get_static_cond().broadcast();
+	return;
+      }	
+#endif
+
+    set_init_in_progress_flag(g, 0);
+#if defined(__GTHREADS) && !defined(__GTHREAD_HAS_COND)
+    // This provides compatibility with older systems not supporting POSIX like
+    // conditional variables.
     if (__gthread_active_p ())
       static_mutex->unlock();
 #endif
@@ -191,10 +605,28 @@
   extern "C"
   void __cxa_guard_release (__guard *g)
   {
-    recursion_pop (g);
+#ifdef __GTHREAD_HAS_COND
+    if (__gthread_active_p())
+      {
+	mutex_wrapper mw;
+
+	// We need to maintain the skip list invariant.
+	skip_list_delete_key(get_static_skip_list(), g);
+	set_init_in_progress_flag(g, 0);
+	_GLIBCXX_GUARD_SET_AND_RELEASE(g);
+
+        get_static_cond().broadcast();
+	return;
+      }	
+#endif
+
+    set_init_in_progress_flag(g, 0);
     _GLIBCXX_GUARD_SET_AND_RELEASE (g);
-#ifdef __GTHREADS
-    if (__gthread_active_p ())
+
+#if defined(__GTHREADS) && !defined(__GTHREAD_HAS_COND)
+    // This provides compatibility with older systems not supporting POSIX like
+    // conditional variables.
+    if (__gthread_active_p())
       static_mutex->unlock();
 #endif
   }
diff -Nru ../gcc-4.2.0/gcc-4.2.0/libstdc++-v3/testsuite/thread/guard.cc gcc-4.2.0/libstdc++-v3/testsuite/thread/guard.cc
--- ../gcc-4.2.0/gcc-4.2.0/libstdc++-v3/testsuite/thread/guard.cc	1969-12-31 16:00:00.000000000 -0800
+++ gcc-4.2.0/libstdc++-v3/testsuite/thread/guard.cc	2007-06-12 11:14:21.258470000 -0700
@@ -0,0 +1,67 @@
+//
+// Copyright (C) 2007 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// { dg-do run { target *-*-freebsd* *-*-netbsd* *-*-linux* *-*-solaris* *-*-cygwin *-*-darwin* alpha*-*-osf* } }
+// { dg-options "-pthread" { target *-*-freebsd* *-*-netbsd* *-*-linux* *-*-solaris* *-*-darwin* alpha*-*-osf* } }
+
+#include <cstdlib>
+#include <pthread.h>
+
+// This used to deadlock with the old libstdc++ because there is only one
+// global mutex guarding initialization of statics and it is held during by
+// the initializer thread of a static until the variable is completely
+// initialized. If the initializer thread creates and waits for another thread
+// which also initializes a static variable, there will be a deadlock because
+// the first thread is holding the mutex and waiting for the second thread,
+// which is blocked when it is acquiring the mutex.
+
+int
+get_bar (void)
+{
+  return 1;
+}
+
+void*
+do_something (void *arg)
+{
+  static int bar = get_bar ();
+  return NULL;
+}
+
+int
+get_foo (void)
+{
+  int status;
+  pthread_t new_thread;
+
+  if (pthread_create (&new_thread, NULL, do_something, NULL) != 0)
+    std::abort ();
+
+  if (pthread_join (new_thread, NULL) != 0)
+    std::abort ();
+
+  return 1;
+}
+
+int
+main (int argc, char **argv)
+{
+  static int foo = get_foo ();
+  return 0;  
+}

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Jason Merrill]

Thanks for fixing this, and sorry about the delay.

It seems like the skip list code is only used to support throwing the 
recursive_init_exception.  I think I'd prefer to just drop that and let 
recursive initialization deadlock (which is allowed under undefined 
behavior) rather than add that overhead to the common case.

Jason

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Doug Kwan (關振德)]

Hi Jason,

That's reasonable.  I can change that.  Actually, we have don't need
the skip list for system with 32-bit pthread ID.  Is it desirable to
support low-overhead recursive init detection in those systems?

-Doug

2007/8/15, Jason Merrill <jason@redhat.com>:
> Thanks for fixing this, and sorry about the delay.
>
> It seems like the skip list code is only used to support throwing the
> recursive_init_exception.  I think I'd prefer to just drop that and let
> recursive initialization deadlock (which is allowed under undefined
> behavior) rather than add that overhead to the common case.
>
> Jason
>

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Jason Merrill]

Doug Kwan (關振德) wrote:

> Actually, we have don't need
> the skip list for system with 32-bit pthread ID.  Is it desirable to
> support low-overhead recursive init detection in those systems?

Well, I implemented that checking initially because it was essentially 
free.  If it's free on such systems and it's easy to distinguish such 
systems, then sure.  If it's at all complicated, don't bother, recursive 
initialization seems very rare.

Jason

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Doug Kwan (關振德)]

[-- Attachment #1: Type: text/plain, Size: 1759 bytes --]

Hi Jason,

   Here is the patch without the skip-list.

-Doug

-----
2007-09-13  Doug Kwan  <dougkwan@google.com>

        * gcc/gthr-posix.h (__gthread_cond_broadcast, __gthread_cond_wait,
          __gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
          Add to extend interface for POSIX conditional variables.
          (__GTHREAD_HAS_COND): Macro defined to signify support of
          conditional variables.
        Likewise
        * gcc/gthr-single.h (__gthread_cond_broadcast, __gthread_cond_wait,
          __gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
          Add to extend interface for POSIX conditional variables.
        * gcc/gthr.h: Update comments to document new interface.

        * libstdc++-v3/include/ext/concurrent.h (class __mutex,
          class __recursive_mutex): Add new method gthread_mutex to access
          inner gthread mutex.
          [__GTHREAD_HAS_COND] (class __concurrence_broadcast_error,
          class __concurrence_wait_error, class __cond): Add.
        * guard.cc (recurisve_push, recursive_pop): Delete.
          (init_in_progress_flag, set_init_in_progress_flag): Add to
          replace recursive_push and recursive_pop.
          (throw_recursive_init_exception): Add.
          (acquire, __cxa_guard_acquire, __cxa_guard_abort and
          __cxa_guard_release): [__GTHREAD_HAS_COND] Use a conditional
          for synchronization of static variable initialization.
          The global mutex is only held briefly when guards are
          accessed. [!__GTHREAD_HAS_COND] Fall back to the old code,
          which deadlocks.
        * testsuite/thread/guard.cc: Add new test. It deadlocks with the
          old locking code in libstdc++-v3/libsup++/guard.cc.

[-- Attachment #2: diffs-deadlock-fix.txt --]
[-- Type: text/plain, Size: 17493 bytes --]

diff -Nru gcc-old/gcc/gcc/gthr-posix.h gcc-new/gcc/gcc/gthr-posix.h
--- gcc-old/gcc/gcc/gthr-posix.h	2007-09-13 15:55:31.000000000 -0700
+++ gcc-new/gcc/gcc/gthr-posix.h	2007-09-13 16:14:49.000000000 -0700
@@ -43,10 +43,16 @@
 #include <pthread.h>
 #include <unistd.h>
 
+typedef pthread_t __gthread_t;
 typedef pthread_key_t __gthread_key_t;
 typedef pthread_once_t __gthread_once_t;
 typedef pthread_mutex_t __gthread_mutex_t;
 typedef pthread_mutex_t __gthread_recursive_mutex_t;
+typedef pthread_cond_t __gthread_cond_t;
+
+/* POSIX like conditional variables are supported.  Please look at comments
+   in gthr.h for details. */
+#define __GTHREAD_HAS_COND	1	
 
 #define __GTHREAD_MUTEX_INIT PTHREAD_MUTEX_INITIALIZER
 #define __GTHREAD_ONCE_INIT PTHREAD_ONCE_INIT
@@ -57,6 +63,7 @@
 #else
 #define __GTHREAD_RECURSIVE_MUTEX_INIT_FUNCTION __gthread_recursive_mutex_init_function
 #endif
+#define __GTHREAD_COND_INIT PTHREAD_COND_INITIALIZER
 
 #if SUPPORTS_WEAK && GTHREAD_USE_WEAK
 # ifndef __gthrw_pragma
@@ -88,6 +95,9 @@
 __gthrw3(pthread_mutex_trylock)
 __gthrw3(pthread_mutex_unlock)
 __gthrw3(pthread_mutex_init)
+__gthrw3(pthread_cond_broadcast)
+__gthrw3(pthread_cond_wait)
+__gthrw3(pthread_self)
 #else
 __gthrw(pthread_once)
 __gthrw(pthread_getspecific)
@@ -98,6 +108,9 @@
 __gthrw(pthread_mutex_trylock)
 __gthrw(pthread_mutex_unlock)
 __gthrw(pthread_mutex_init)
+__gthrw(pthread_cond_broadcast)
+__gthrw(pthread_cond_wait)
+__gthrw(pthread_self)
 #endif
 
 __gthrw(pthread_key_create)
@@ -105,28 +118,22 @@
 __gthrw(pthread_mutexattr_init)
 __gthrw(pthread_mutexattr_settype)
 __gthrw(pthread_mutexattr_destroy)
-
+__gthrw(pthread_equal)
 
 #if defined(_LIBOBJC) || defined(_LIBOBJC_WEAK)
 /* Objective-C.  */
 #if defined(__osf__) && defined(_PTHREAD_USE_MANGLED_NAMES_)
-__gthrw3(pthread_cond_broadcast)
 __gthrw3(pthread_cond_destroy)
 __gthrw3(pthread_cond_init)
 __gthrw3(pthread_cond_signal)
-__gthrw3(pthread_cond_wait)
 __gthrw3(pthread_exit)
 __gthrw3(pthread_mutex_destroy)
-__gthrw3(pthread_self)
 #else
-__gthrw(pthread_cond_broadcast)
 __gthrw(pthread_cond_destroy)
 __gthrw(pthread_cond_init)
 __gthrw(pthread_cond_signal)
-__gthrw(pthread_cond_wait)
 __gthrw(pthread_exit)
 __gthrw(pthread_mutex_destroy)
-__gthrw(pthread_self)
 #endif /* __osf__ && _PTHREAD_USE_MANGLED_NAMES_ */
 #ifdef _POSIX_PRIORITY_SCHEDULING
 #ifdef _POSIX_THREAD_PRIORITY_SCHEDULING
@@ -737,6 +744,37 @@
   return __gthread_mutex_unlock (mutex);
 }
 
+static inline int
+__gthread_cond_broadcast (__gthread_cond_t *cond)
+{
+  return __gthrw_(pthread_cond_broadcast) (cond);
+}
+
+static inline int
+__gthread_cond_wait (__gthread_cond_t *cond, __gthread_mutex_t *mutex)
+{
+  return __gthrw_(pthread_cond_wait) (cond, mutex);
+}
+
+static inline int
+__gthread_cond_wait_recursive (__gthread_cond_t *cond,
+			       __gthread_recursive_mutex_t *mutex)
+{
+  return __gthread_cond_wait (cond, mutex);
+}
+
+static inline __gthread_t
+__gthread_self (void)
+{
+  return __gthrw_(pthread_self) ();
+}
+
+static inline int
+__gthread_equal (__gthread_t t1, __gthread_t t2)
+{
+  return __gthrw_(pthread_equal) (t1, t2);
+}
+
 #endif /* _LIBOBJC */
 
 #endif /* ! GCC_GTHR_POSIX_H */
diff -Nru gcc-old/gcc/gcc/gthr-single.h gcc-new/gcc/gcc/gthr-single.h
--- gcc-old/gcc/gcc/gthr-single.h	2007-09-13 15:55:31.000000000 -0700
+++ gcc-new/gcc/gcc/gthr-single.h	2007-09-13 16:14:49.000000000 -0700
@@ -251,6 +251,37 @@
   return __gthread_mutex_unlock (mutex);
 }
 
+static inline int
+__gthread_cond_broadcast (__gthread_cond_t cond)
+{
+  return 0;
+}
+
+static inline int
+__gthread_cond_wait (__gthread_cond_t cond, __gthread_mutex_t *mutex)
+{
+  return 0;
+}
+
+static inline int
+__gthread_cond_wait_recursive (__gthread_cond_t cond,
+			       __gthread_recursive_mutex_t *mutex)
+{
+  return 0;
+}
+
+static inline __gthread_t
+__gthread_self (void)
+{
+  return (__gthread_t)0;
+}
+
+static inline int
+__gthread_equal (__gthread_t t1, __gthread_t t2)
+{
+  return (t1 == t2);
+}
+
 #endif /* _LIBOBJC */
 
 #undef UNUSED
diff -Nru gcc-old/gcc/gcc/gthr.h gcc-new/gcc/gcc/gthr.h
--- gcc-old/gcc/gcc/gthr.h	2007-09-13 15:55:31.000000000 -0700
+++ gcc-new/gcc/gcc/gthr.h	2007-09-13 16:14:49.000000000 -0700
@@ -81,6 +81,27 @@
      int __gthread_recursive_mutex_trylock (__gthread_recursive_mutex_t *mutex);
      int __gthread_recursive_mutex_unlock (__gthread_recursive_mutex_t *mutex);
 
+   The following are supported in POSIX threads only. They are required to
+   fix a deadlock in static initialization inside libsupc++. The header file
+   gthr-posix.h defines a symbol __GTHREAD_HAS_COND to signify that these extra
+   features are supported.
+
+   Types:
+     __gthread_t
+     __gthread_cond_t
+
+   Macros:
+     __GTHREAD_COND_INIT
+     __GTHREAD_COND_INIT_FUNCTION
+
+   Interface:
+     int __gthread_cond_broadcast (__gthread_cond_t *cond);
+     int __gthread_cond_wait (__gthread_cond_t *cond, __gthread_mutex_t *mutex);
+     int __gthread_cond_wait_recursive (__gthread_cond_t *cond,
+					__gthread_recursive_mutex_t *mutex);
+     __gthread_t __gthread_self (void);
+     int __gthread_equal (__gthread_t t1, __gthread_t t2);
+
    All functions returning int should return zero on success or the error
    number.  If the operation is not supported, -1 is returned.
 
diff -Nru gcc-old/gcc/libstdc++-v3/include/ext/concurrence.h gcc-new/gcc/libstdc++-v3/include/ext/concurrence.h
--- gcc-old/gcc/libstdc++-v3/include/ext/concurrence.h	2007-09-13 15:55:33.000000000 -0700
+++ gcc-new/gcc/libstdc++-v3/include/ext/concurrence.h	2007-09-13 16:14:49.000000000 -0700
@@ -81,6 +81,22 @@
     { return "__gnu_cxx::__concurrence_unlock_error"; }
   };
 
+  class __concurrence_broadcast_error : public std::exception
+  {
+  public:
+    virtual char const*
+    what() const throw()
+    { return "__gnu_cxx::__concurrence_broadcast_error"; }
+  };
+
+  class __concurrence_wait_error : public std::exception
+  {
+  public:
+    virtual char const*
+    what() const throw()
+    { return "__gnu_cxx::__concurrence_wait_error"; }
+  };
+
   // Substitute for concurrence_error object in the case of -fno-exceptions.
   inline void
   __throw_concurrence_lock_error()
@@ -102,6 +118,28 @@
 #endif
   }
 
+#ifdef __GTHREAD_HAS_COND
+  inline void
+  __throw_concurrence_broadcast_error()
+  {
+#if __EXCEPTIONS
+    throw __concurrence_broadcast_error();
+#else
+    __builtin_abort();
+#endif
+  }
+
+  inline void
+  __throw_concurrence_wait_error()
+  {
+#if __EXCEPTIONS
+    throw __concurrence_wait_error();
+#else
+    __builtin_abort();
+#endif
+  }
+#endif
+ 
   class __mutex 
   {
   private:
@@ -147,6 +185,9 @@
 	}
 #endif
     }
+
+    __gthread_mutex_t* gthread_mutex(void)
+      { return &_M_mutex; }
   };
 
   class __recursive_mutex 
@@ -194,6 +235,9 @@
 	}
 #endif
     }
+
+    __gthread_recursive_mutex_t* gthread_recursive_mutex(void)
+      { return &_M_mutex; }
   };
 
   /// @brief  Scoped lock idiom.
@@ -218,6 +262,66 @@
     { _M_device.unlock(); }
   };
 
+#ifdef __GTHREAD_HAS_COND
+  class __cond
+  {
+  private:
+    __gthread_cond_t _M_cond;
+
+    __cond(const __cond&);
+    __cond& operator=(const __cond&);
+
+  public:
+    __cond() 
+    { 
+#if __GTHREADS
+      if (__gthread_active_p())
+	{
+#if defined __GTHREAD_COND_INIT
+	  __gthread_cond_t __tmp = __GTHREAD_COND_INIT;
+	  _M_cond = __tmp;
+#else
+	  __GTHREAD_MUTEX_INIT_FUNCTION(&_M_cond);
+#endif
+	}
+#endif 
+    }
+
+    void broadcast()
+    {
+#if __GTHREADS
+      if (__gthread_active_p())
+	{
+	  if (__gthread_cond_broadcast(&_M_cond) != 0)
+	    __throw_concurrence_broadcast_error();
+	}
+#endif
+    }
+
+    void wait(__mutex *mutex)
+    {
+#if __GTHREADS
+      {
+	  if (__gthread_cond_wait(&_M_cond, mutex->gthread_mutex()) != 0)
+	    __throw_concurrence_wait_error();
+      }
+#endif
+    }
+
+    void wait_recursive(__recursive_mutex *mutex)
+    {
+#if __GTHREADS
+      {
+	  if (__gthread_cond_wait_recursive(&_M_cond,
+					    mutex->gthread_recursive_mutex())
+	      != 0)
+	    __throw_concurrence_wait_error();
+      }
+#endif
+    }
+  };
+#endif
+
 _GLIBCXX_END_NAMESPACE
 
 #endif
diff -Nru gcc-old/gcc/libstdc++-v3/libsupc++/guard.cc gcc-new/gcc/libstdc++-v3/libsupc++/guard.cc
--- gcc-old/gcc/libstdc++-v3/libsupc++/guard.cc	2007-09-13 15:55:37.000000000 -0700
+++ gcc-new/gcc/libstdc++-v3/libsupc++/guard.cc	2007-09-13 16:14:49.000000000 -0700
@@ -62,6 +62,28 @@
   }
 }
 
+namespace
+{
+  // A single conditional variable controlling all static initializations.
+  static __gnu_cxx::__cond* static_cond;  
+
+  // using a fake type to avoid initializing a static class.
+  typedef char fake_cond_t[sizeof(__gnu_cxx::__cond)]
+  __attribute__ ((aligned(__alignof__(__gnu_cxx::__cond))));
+  fake_cond_t fake_cond;
+
+  static void init_static_cond()
+  { static_cond =  new (&fake_cond) __gnu_cxx::__cond(); }
+
+  __gnu_cxx::__cond&
+  get_static_cond()
+  {
+    static __gthread_once_t once = __GTHREAD_ONCE_INIT;
+    __gthread_once(&once, init_static_cond);
+    return *static_cond;
+  }
+}
+
 #ifndef _GLIBCXX_GUARD_TEST_AND_ACQUIRE
 inline bool
 __test_and_acquire (__cxxabiv1::__guard *g)
@@ -110,34 +132,87 @@
   recursive_init_error::~recursive_init_error() throw() { }
 }
 
+//
+// Here are C++ run-time routines for guarded initiailization of static
+// variables. There are 4 scenarios under which these routines are called:
+//
+//   1. Threads not supported (__GTHREADS not defined)
+//   2. Threads are supported but not enabled at run-time.
+//   3. Threads enabled at run-time but __gthreads_* are not fully POSIX.
+//   4. Threads enabled at run-time and __gthreads_* support all POSIX threads
+//      primitives we need here.
+//
+// The old code supported scenarios 1-3 but was broken since it used a global
+// mutex for all threads and had the mutex locked during the whole duration of
+// initlization of a guarded static variable. The following created a dead-lock
+// with the old code.
+//
+//	Thread 1 acquires the global mutex.
+//	Thread 1 starts initializing static variable.
+//	Thread 1 creates thread 2 during initialization.
+//	Thread 2 attempts to acuqire mutex to initialize another variable.
+//	Thread 2 blocks since thread 1 is locking the mutex.
+//	Thread 1 waits for result from thread 2 and also blocks. A deadlock.
+//
+// The new code here can handle this situation and thus is more robust. Howere,
+// we need to use the POSIX thread conditional variable, which is not supported
+// in all platforms, notably older versions of Microsoft Windows. The gthr*.h
+// headers define a symbol __GTHREAD_HAS_COND for platforms that support POSIX
+// like conditional variables. For platforms that do not support conditional
+// variables, we need to fall back to the old code.
 namespace __cxxabiv1 
 {
   static inline int
-  recursion_push (__guard* g)
-  { return ((char *)g)[1]++; }
+  init_in_progress_flag(__guard* g)
+  { return ((char *)g)[1]; }
 
   static inline void
-  recursion_pop (__guard* g)
-  { --((char *)g)[1]; }
+  set_init_in_progress_flag(__guard* g, int v)
+  { ((char *)g)[1] = v; }
 
-  static int
-  acquire (__guard *g)
+  static inline void
+  throw_recursive_init_exception()
   {
-    if (_GLIBCXX_GUARD_TEST (g))
-      return 0;
-
-    if (recursion_push (g))
-      {
 #ifdef __EXCEPTIONS
 	throw __gnu_cxx::recursive_init_error();
 #else
 	// Use __builtin_trap so we don't require abort().
-	__builtin_trap ();
+	__builtin_trap();
 #endif
-      }
+  }
+
+  // acuire() is a helper function used to acquire guard if thread support is
+  // not compiled in or is compiled in but not enabled at run-time.
+  static int
+  acquire(__guard *g)
+  {
+    // Quit if the object is already initialized.
+    if (_GLIBCXX_GUARD_TEST(g))
+      return 0;
+
+    if (init_in_progress_flag(g))
+	throw_recursive_init_exception();
+
+    set_init_in_progress_flag(g, 1);
     return 1;
   }
 
+  // Simple wrapper for exception safety.
+  struct mutex_wrapper
+  {
+#ifdef __GTHREADS
+    bool unlock;
+    mutex_wrapper() : unlock(true)
+    { get_static_mutex().lock(); }
+
+    ~mutex_wrapper()
+    {
+      if (unlock)
+	static_mutex->unlock();
+    }
+#endif
+  };
+
   extern "C"
   int __cxa_guard_acquire (__guard *g) 
   {
@@ -150,28 +225,39 @@
 
     if (__gthread_active_p ())
       {
-	// Simple wrapper for exception safety.
-	struct mutex_wrapper
-	{
-	  bool unlock;
-	  mutex_wrapper() : unlock(true)
-	  { get_static_mutex().lock(); }
-
-	  ~mutex_wrapper()
-	  {
-	    if (unlock)
-	      static_mutex->unlock();
-	  }
-	};
-
 	mutex_wrapper mw;
-	if (acquire (g))
+
+	while (1)	// When this loop is executing, mutex is locked.
 	  {
-	    mw.unlock = false;
-	    return 1;
+#ifdef __GTHREAD_HAS_COND
+	    // The static is allready initialized.
+	    if (_GLIBCXX_GUARD_TEST(g))
+	      return 0;	// The mutex will be unlocked via wrapper
+
+	    if (init_in_progress_flag(g))
+	      {
+		// The guarded static is currently being initialized by
+		// another thread, so we release mutex and wait for the
+		// conditional variable. We will lock the mutex again after
+		// this.
+		get_static_cond().wait_recursive(&get_static_mutex());
+	      }
+	    else
+	      {
+		set_init_in_progress_flag(g, 1);
+		return 1; // The mutex will be unlocked via wrapper.
+	      }
+#else
+	    // This provides compatibility with older systems not supporting
+	    // POSIX like conditional variables.
+	    if (acquire(g))
+	      {
+		mw.unlock = false;
+		return 1; // The mutex still locked.
+	      }
+	    return 0; // The mutex will be unlocked via wrapper.
+#endif
 	  }
-
-	return 0;
       }
 #endif
 
@@ -181,8 +267,24 @@
   extern "C"
   void __cxa_guard_abort (__guard *g)
   {
-    recursion_pop (g);
-#ifdef __GTHREADS
+#ifdef __GTHREAD_HAS_COND
+    if (__gthread_active_p())
+      {	
+	mutex_wrapper mw;
+
+	set_init_in_progress_flag(g, 0);
+
+	// If we abort, we still need to wake up all other threads waiting for
+	// the conditional variable.
+        get_static_cond().broadcast();
+	return;
+      }	
+#endif
+
+    set_init_in_progress_flag(g, 0);
+#if defined(__GTHREADS) && !defined(__GTHREAD_HAS_COND)
+    // This provides compatibility with older systems not supporting POSIX like
+    // conditional variables.
     if (__gthread_active_p ())
       static_mutex->unlock();
 #endif
@@ -191,10 +293,26 @@
   extern "C"
   void __cxa_guard_release (__guard *g)
   {
-    recursion_pop (g);
+#ifdef __GTHREAD_HAS_COND
+    if (__gthread_active_p())
+      {
+	mutex_wrapper mw;
+
+	set_init_in_progress_flag(g, 0);
+	_GLIBCXX_GUARD_SET_AND_RELEASE(g);
+
+        get_static_cond().broadcast();
+	return;
+      }	
+#endif
+
+    set_init_in_progress_flag(g, 0);
     _GLIBCXX_GUARD_SET_AND_RELEASE (g);
-#ifdef __GTHREADS
-    if (__gthread_active_p ())
+
+#if defined(__GTHREADS) && !defined(__GTHREAD_HAS_COND)
+    // This provides compatibility with older systems not supporting POSIX like
+    // conditional variables.
+    if (__gthread_active_p())
       static_mutex->unlock();
 #endif
   }
diff -Nru gcc-old/gcc/libstdc++-v3/testsuite/thread/guard.cc gcc-new/gcc/libstdc++-v3/testsuite/thread/guard.cc
--- gcc-old/gcc/libstdc++-v3/testsuite/thread/guard.cc	1969-12-31 16:00:00.000000000 -0800
+++ gcc-new/gcc/libstdc++-v3/testsuite/thread/guard.cc	2007-09-13 16:16:17.000000000 -0700
@@ -0,0 +1,67 @@
+//
+// Copyright (C) 2007 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// { dg-do run { target *-*-freebsd* *-*-netbsd* *-*-linux* *-*-solaris* *-*-cygwin *-*-darwin* alpha*-*-osf* } }
+// { dg-options "-pthread" { target *-*-freebsd* *-*-netbsd* *-*-linux* *-*-solaris* *-*-darwin* alpha*-*-osf* } }
+
+#include <cstdlib>
+#include <pthread.h>
+
+// This used to deadlock with the old libstdc++ because there is only one
+// global mutex guarding initialization of statics and it is held during by
+// the initializer thread of a static until the variable is completely
+// initialized. If the initializer thread creates and waits for another thread
+// which also initializes a static variable, there will be a deadlock because
+// the first thread is holding the mutex and waiting for the second thread,
+// which is blocked when it is acquiring the mutex.
+
+int
+get_bar (void)
+{
+  return 1;
+}
+
+void*
+do_something (void *arg)
+{
+  static int bar = get_bar ();
+  return NULL;
+}
+
+int
+get_foo (void)
+{
+  int status;
+  pthread_t new_thread;
+
+  if (pthread_create (&new_thread, NULL, do_something, NULL) != 0)
+    std::abort ();
+
+  if (pthread_join (new_thread, NULL) != 0)
+    std::abort ();
+
+  return 1;
+}
+
+int
+main (int argc, char **argv)
+{
+  static int foo = get_foo ();
+  return 0;  
+}

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Eric Botcazou]

> 2007-09-13  Doug Kwan  <dougkwan@google.com>
>
>         * gcc/gthr-posix.h (__gthread_cond_broadcast, __gthread_cond_wait,
>           __gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
>           Add to extend interface for POSIX conditional variables.
>           (__GTHREAD_HAS_COND): Macro defined to signify support of
>           conditional variables.

Is this supported by POSIX 95?  If so, gthr-posix95.h should be updated too.

-- 
Eric Botcazou

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Doug Kwan (關振德)]

I can do that but I don't have a system for testing.

-Doug

2007/9/17, Eric Botcazou <ebotcazou@libertysurf.fr>:
> > 2007-09-13  Doug Kwan  <dougkwan@google.com>
> >
> >         * gcc/gthr-posix.h (__gthread_cond_broadcast, __gthread_cond_wait,
> >           __gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
> >           Add to extend interface for POSIX conditional variables.
> >           (__GTHREAD_HAS_COND): Macro defined to signify support of
> >           conditional variables.
>
> Is this supported by POSIX 95?  If so, gthr-posix95.h should be updated too.
>
> --
> Eric Botcazou
>

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Doug Kwan (關振德)]

[-- Attachment #1: Type: text/plain, Size: 2043 bytes --]

Here is a new patch that fixes two issues mentioned earlier in this
thread. I don't have access to any machine running Solaris 2.x. So the
changes in gthr-posix95.h is not tested.

-Doug
==========================
2007-09-13  Doug Kwan  <dougkwan@google.com>

        * gcc/gthr-posix.h (__gthread_cond_broadcast, __gthread_cond_wait,
        __gthread_cond_wait_recursive): Add to extend interface for POSIX
        conditional variables. (__GTHREAD_HAS_COND): Macro defined to signify
        support of conditional variables.
        * gcc/gthr-posix95.h (__gthread_cond_broadcast, __gthread_cond_wait,
        __gthread_cond_wait_recursive): Add to extend interface for POSIX
        conditional variables. (__GTHREAD_HAS_COND): Macro defined to signify
        support of conditional variables.
        * gcc/gthr-single.h (__gthread_cond_broadcast, __gthread_cond_wait,
        __gthread_cond_wait_recursive): Add to extend interface for POSIX
        conditional variables.
        * gcc/gthr.h: Update comments to document new interface.
        * libstdc++-v3/include/ext/concurrent.h (class __mutex,
        class __recursive_mutex): Add new method gthread_mutex to access
        inner gthread mutex.
        [__GTHREAD_HAS_COND] (class __concurrence_broadcast_error,
        class __concurrence_wait_error, class __cond): Add.
        * guard.cc (recursive_push, recursive_pop): Delete.
        (init_in_progress_flag, set_init_in_progress_flag): Add to
        replace recursive_push and recursive_pop.
        (throw_recursive_init_exception): Add.
        (acquire, __cxa_guard_acquire, __cxa_guard_abort and
        __cxa_guard_release): [__GTHREAD_HAS_COND] Use a conditional
        for synchronization of static variable initialization.
        The global mutex is only held briefly when guards are
        accessed. [!__GTHREAD_HAS_COND] Fall back to the old code,
        which deadlocks.
        * testsuite/thread/guard.cc: Add new test. It deadlocks with the
        old locking code in libstdc++-v3/libsup++/guard.cc.

[-- Attachment #2: diffs-deadlock-fix.txt --]
[-- Type: text/plain, Size: 18482 bytes --]

diff -Nru gcc-old/gcc/gcc/gthr-posix.h gcc-new/gcc/gcc/gthr-posix.h
--- gcc-old/gcc/gcc/gthr-posix.h	2007-09-13 15:55:31.000000000 -0700
+++ gcc-new/gcc/gcc/gthr-posix.h	2007-09-18 13:18:26.000000000 -0700
@@ -47,6 +47,11 @@
 typedef pthread_once_t __gthread_once_t;
 typedef pthread_mutex_t __gthread_mutex_t;
 typedef pthread_mutex_t __gthread_recursive_mutex_t;
+typedef pthread_cond_t __gthread_cond_t;
+
+/* POSIX like conditional variables are supported.  Please look at comments
+   in gthr.h for details. */
+#define __GTHREAD_HAS_COND	1	
 
 #define __GTHREAD_MUTEX_INIT PTHREAD_MUTEX_INITIALIZER
 #define __GTHREAD_ONCE_INIT PTHREAD_ONCE_INIT
@@ -57,6 +62,7 @@
 #else
 #define __GTHREAD_RECURSIVE_MUTEX_INIT_FUNCTION __gthread_recursive_mutex_init_function
 #endif
+#define __GTHREAD_COND_INIT PTHREAD_COND_INITIALIZER
 
 #if SUPPORTS_WEAK && GTHREAD_USE_WEAK
 # ifndef __gthrw_pragma
@@ -88,6 +94,8 @@
 __gthrw3(pthread_mutex_trylock)
 __gthrw3(pthread_mutex_unlock)
 __gthrw3(pthread_mutex_init)
+__gthrw3(pthread_cond_broadcast)
+__gthrw3(pthread_cond_wait)
 #else
 __gthrw(pthread_once)
 __gthrw(pthread_getspecific)
@@ -98,6 +106,8 @@
 __gthrw(pthread_mutex_trylock)
 __gthrw(pthread_mutex_unlock)
 __gthrw(pthread_mutex_init)
+__gthrw(pthread_cond_broadcast)
+__gthrw(pthread_cond_wait)
 #endif
 
 __gthrw(pthread_key_create)
@@ -110,20 +120,16 @@
 #if defined(_LIBOBJC) || defined(_LIBOBJC_WEAK)
 /* Objective-C.  */
 #if defined(__osf__) && defined(_PTHREAD_USE_MANGLED_NAMES_)
-__gthrw3(pthread_cond_broadcast)
 __gthrw3(pthread_cond_destroy)
 __gthrw3(pthread_cond_init)
 __gthrw3(pthread_cond_signal)
-__gthrw3(pthread_cond_wait)
 __gthrw3(pthread_exit)
 __gthrw3(pthread_mutex_destroy)
 __gthrw3(pthread_self)
 #else
-__gthrw(pthread_cond_broadcast)
 __gthrw(pthread_cond_destroy)
 __gthrw(pthread_cond_init)
 __gthrw(pthread_cond_signal)
-__gthrw(pthread_cond_wait)
 __gthrw(pthread_exit)
 __gthrw(pthread_mutex_destroy)
 __gthrw(pthread_self)
@@ -737,6 +743,25 @@
   return __gthread_mutex_unlock (mutex);
 }
 
+static inline int
+__gthread_cond_broadcast (__gthread_cond_t *cond)
+{
+  return __gthrw_(pthread_cond_broadcast) (cond);
+}
+
+static inline int
+__gthread_cond_wait (__gthread_cond_t *cond, __gthread_mutex_t *mutex)
+{
+  return __gthrw_(pthread_cond_wait) (cond, mutex);
+}
+
+static inline int
+__gthread_cond_wait_recursive (__gthread_cond_t *cond,
+			       __gthread_recursive_mutex_t *mutex)
+{
+  return __gthread_cond_wait (cond, mutex);
+}
+
 #endif /* _LIBOBJC */
 
 #endif /* ! GCC_GTHR_POSIX_H */
diff -Nru gcc-old/gcc/gcc/gthr-posix95.h gcc-new/gcc/gcc/gthr-posix95.h
--- gcc-old/gcc/gcc/gthr-posix95.h	2007-09-13 15:55:31.000000000 -0700
+++ gcc-new/gcc/gcc/gthr-posix95.h	2007-09-18 13:18:26.000000000 -0700
@@ -45,6 +45,11 @@
 typedef pthread_key_t __gthread_key_t;
 typedef pthread_once_t __gthread_once_t;
 typedef pthread_mutex_t __gthread_mutex_t;
+typedef pthread_cond_t __gthread_cond_t;
+
+/* POSIX like conditional variables are supported.  Please look at comments
+   in gthr.h for details. */
+#define __GTHREAD_HAS_COND	1
 
 typedef struct {
   long depth;
@@ -55,6 +60,7 @@
 #define __GTHREAD_MUTEX_INIT PTHREAD_MUTEX_INITIALIZER
 #define __GTHREAD_ONCE_INIT PTHREAD_ONCE_INIT
 #define __GTHREAD_RECURSIVE_MUTEX_INIT_FUNCTION __gthread_recursive_mutex_init_function
+#define __GTHREAD_COND_INIT PTHREAD_COND_INITIALIZER
 
 #if SUPPORTS_WEAK && GTHREAD_USE_WEAK
 # define __gthrw(name) \
@@ -81,14 +87,14 @@
 __gthrw(pthread_mutexattr_destroy)
 
 __gthrw(pthread_mutex_init)
+__gthrw(pthread_cond_broadcast)
+__gthrw(pthread_cond_wait)
 
 #if defined(_LIBOBJC) || defined(_LIBOBJC_WEAK)
 /* Objective-C.  */
-__gthrw(pthread_cond_broadcast)
 __gthrw(pthread_cond_destroy)
 __gthrw(pthread_cond_init)
 __gthrw(pthread_cond_signal)
-__gthrw(pthread_cond_wait)
 __gthrw(pthread_exit)
 __gthrw(pthread_mutex_destroy)
 #ifdef _POSIX_PRIORITY_SCHEDULING
@@ -719,6 +725,25 @@
   return 0;
 }
 
+static inline int
+__gthread_cond_broadcast (__gthread_cond_t *cond)
+{
+  return __gthrw_(pthread_cond_broadcast) (cond);
+}
+
+static inline int
+__gthread_cond_wait (__gthread_cond_t *cond, __gthread_mutex_t *mutex)
+{
+  return __gthrw_(pthread_cond_wait) (cond, mutex);
+}
+
+static inline int
+__gthread_cond_wait_recursive (__gthread_cond_t *cond,
+			       __gthread_recursive_mutex_t *mutex)
+{
+  return __gthrw_(pthread_cond_wait) (cond, mutex->actual);
+}
+
 #endif /* _LIBOBJC */
 
 #endif /* ! GCC_GTHR_POSIX_H */
diff -Nru gcc-old/gcc/gcc/gthr-single.h gcc-new/gcc/gcc/gthr-single.h
--- gcc-old/gcc/gcc/gthr-single.h	2007-09-13 15:55:31.000000000 -0700
+++ gcc-new/gcc/gcc/gthr-single.h	2007-09-18 13:18:26.000000000 -0700
@@ -251,6 +251,25 @@
   return __gthread_mutex_unlock (mutex);
 }
 
+static inline int
+__gthread_cond_broadcast (__gthread_cond_t cond)
+{
+  return 0;
+}
+
+static inline int
+__gthread_cond_wait (__gthread_cond_t cond, __gthread_mutex_t *mutex)
+{
+  return 0;
+}
+
+static inline int
+__gthread_cond_wait_recursive (__gthread_cond_t cond,
+			       __gthread_recursive_mutex_t *mutex)
+{
+  return 0;
+}
+
 #endif /* _LIBOBJC */
 
 #undef UNUSED
diff -Nru gcc-old/gcc/gcc/gthr.h gcc-new/gcc/gcc/gthr.h
--- gcc-old/gcc/gcc/gthr.h	2007-09-13 15:55:31.000000000 -0700
+++ gcc-new/gcc/gcc/gthr.h	2007-09-18 13:18:26.000000000 -0700
@@ -81,6 +81,24 @@
      int __gthread_recursive_mutex_trylock (__gthread_recursive_mutex_t *mutex);
      int __gthread_recursive_mutex_unlock (__gthread_recursive_mutex_t *mutex);
 
+   The following are supported in POSIX threads only. They are required to
+   fix a deadlock in static initialization inside libsupc++. The header file
+   gthr-posix.h defines a symbol __GTHREAD_HAS_COND to signify that these extra
+   features are supported.
+
+   Types:
+     __gthread_cond_t
+
+   Macros:
+     __GTHREAD_COND_INIT
+     __GTHREAD_COND_INIT_FUNCTION
+
+   Interface:
+     int __gthread_cond_broadcast (__gthread_cond_t *cond);
+     int __gthread_cond_wait (__gthread_cond_t *cond, __gthread_mutex_t *mutex);
+     int __gthread_cond_wait_recursive (__gthread_cond_t *cond,
+					__gthread_recursive_mutex_t *mutex);
+
    All functions returning int should return zero on success or the error
    number.  If the operation is not supported, -1 is returned.
 
diff -Nru gcc-old/gcc/libstdc++-v3/include/ext/concurrence.h gcc-new/gcc/libstdc++-v3/include/ext/concurrence.h
--- gcc-old/gcc/libstdc++-v3/include/ext/concurrence.h	2007-09-13 15:55:33.000000000 -0700
+++ gcc-new/gcc/libstdc++-v3/include/ext/concurrence.h	2007-09-18 13:18:26.000000000 -0700
@@ -81,6 +81,22 @@
     { return "__gnu_cxx::__concurrence_unlock_error"; }
   };
 
+  class __concurrence_broadcast_error : public std::exception
+  {
+  public:
+    virtual char const*
+    what() const throw()
+    { return "__gnu_cxx::__concurrence_broadcast_error"; }
+  };
+
+  class __concurrence_wait_error : public std::exception
+  {
+  public:
+    virtual char const*
+    what() const throw()
+    { return "__gnu_cxx::__concurrence_wait_error"; }
+  };
+
   // Substitute for concurrence_error object in the case of -fno-exceptions.
   inline void
   __throw_concurrence_lock_error()
@@ -102,6 +118,28 @@
 #endif
   }
 
+#ifdef __GTHREAD_HAS_COND
+  inline void
+  __throw_concurrence_broadcast_error()
+  {
+#if __EXCEPTIONS
+    throw __concurrence_broadcast_error();
+#else
+    __builtin_abort();
+#endif
+  }
+
+  inline void
+  __throw_concurrence_wait_error()
+  {
+#if __EXCEPTIONS
+    throw __concurrence_wait_error();
+#else
+    __builtin_abort();
+#endif
+  }
+#endif
+ 
   class __mutex 
   {
   private:
@@ -147,6 +185,9 @@
 	}
 #endif
     }
+
+    __gthread_mutex_t* gthread_mutex(void)
+      { return &_M_mutex; }
   };
 
   class __recursive_mutex 
@@ -194,6 +235,9 @@
 	}
 #endif
     }
+
+    __gthread_recursive_mutex_t* gthread_recursive_mutex(void)
+      { return &_M_mutex; }
   };
 
   /// @brief  Scoped lock idiom.
@@ -218,6 +262,66 @@
     { _M_device.unlock(); }
   };
 
+#ifdef __GTHREAD_HAS_COND
+  class __cond
+  {
+  private:
+    __gthread_cond_t _M_cond;
+
+    __cond(const __cond&);
+    __cond& operator=(const __cond&);
+
+  public:
+    __cond() 
+    { 
+#if __GTHREADS
+      if (__gthread_active_p())
+	{
+#if defined __GTHREAD_COND_INIT
+	  __gthread_cond_t __tmp = __GTHREAD_COND_INIT;
+	  _M_cond = __tmp;
+#else
+	  __GTHREAD_MUTEX_INIT_FUNCTION(&_M_cond);
+#endif
+	}
+#endif 
+    }
+
+    void broadcast()
+    {
+#if __GTHREADS
+      if (__gthread_active_p())
+	{
+	  if (__gthread_cond_broadcast(&_M_cond) != 0)
+	    __throw_concurrence_broadcast_error();
+	}
+#endif
+    }
+
+    void wait(__mutex *mutex)
+    {
+#if __GTHREADS
+      {
+	  if (__gthread_cond_wait(&_M_cond, mutex->gthread_mutex()) != 0)
+	    __throw_concurrence_wait_error();
+      }
+#endif
+    }
+
+    void wait_recursive(__recursive_mutex *mutex)
+    {
+#if __GTHREADS
+      {
+	  if (__gthread_cond_wait_recursive(&_M_cond,
+					    mutex->gthread_recursive_mutex())
+	      != 0)
+	    __throw_concurrence_wait_error();
+      }
+#endif
+    }
+  };
+#endif
+
 _GLIBCXX_END_NAMESPACE
 
 #endif
diff -Nru gcc-old/gcc/libstdc++-v3/libsupc++/guard.cc gcc-new/gcc/libstdc++-v3/libsupc++/guard.cc
--- gcc-old/gcc/libstdc++-v3/libsupc++/guard.cc	2007-09-13 15:55:37.000000000 -0700
+++ gcc-new/gcc/libstdc++-v3/libsupc++/guard.cc	2007-09-18 13:18:26.000000000 -0700
@@ -62,6 +62,28 @@
   }
 }
 
+namespace
+{
+  // A single conditional variable controlling all static initializations.
+  static __gnu_cxx::__cond* static_cond;  
+
+  // using a fake type to avoid initializing a static class.
+  typedef char fake_cond_t[sizeof(__gnu_cxx::__cond)]
+  __attribute__ ((aligned(__alignof__(__gnu_cxx::__cond))));
+  fake_cond_t fake_cond;
+
+  static void init_static_cond()
+  { static_cond =  new (&fake_cond) __gnu_cxx::__cond(); }
+
+  __gnu_cxx::__cond&
+  get_static_cond()
+  {
+    static __gthread_once_t once = __GTHREAD_ONCE_INIT;
+    __gthread_once(&once, init_static_cond);
+    return *static_cond;
+  }
+}
+
 #ifndef _GLIBCXX_GUARD_TEST_AND_ACQUIRE
 inline bool
 __test_and_acquire (__cxxabiv1::__guard *g)
@@ -110,34 +132,87 @@
   recursive_init_error::~recursive_init_error() throw() { }
 }
 
+//
+// Here are C++ run-time routines for guarded initiailization of static
+// variables. There are 4 scenarios under which these routines are called:
+//
+//   1. Threads not supported (__GTHREADS not defined)
+//   2. Threads are supported but not enabled at run-time.
+//   3. Threads enabled at run-time but __gthreads_* are not fully POSIX.
+//   4. Threads enabled at run-time and __gthreads_* support all POSIX threads
+//      primitives we need here.
+//
+// The old code supported scenarios 1-3 but was broken since it used a global
+// mutex for all threads and had the mutex locked during the whole duration of
+// initlization of a guarded static variable. The following created a dead-lock
+// with the old code.
+//
+//	Thread 1 acquires the global mutex.
+//	Thread 1 starts initializing static variable.
+//	Thread 1 creates thread 2 during initialization.
+//	Thread 2 attempts to acuqire mutex to initialize another variable.
+//	Thread 2 blocks since thread 1 is locking the mutex.
+//	Thread 1 waits for result from thread 2 and also blocks. A deadlock.
+//
+// The new code here can handle this situation and thus is more robust. Howere,
+// we need to use the POSIX thread conditional variable, which is not supported
+// in all platforms, notably older versions of Microsoft Windows. The gthr*.h
+// headers define a symbol __GTHREAD_HAS_COND for platforms that support POSIX
+// like conditional variables. For platforms that do not support conditional
+// variables, we need to fall back to the old code.
 namespace __cxxabiv1 
 {
   static inline int
-  recursion_push (__guard* g)
-  { return ((char *)g)[1]++; }
+  init_in_progress_flag(__guard* g)
+  { return ((char *)g)[1]; }
 
   static inline void
-  recursion_pop (__guard* g)
-  { --((char *)g)[1]; }
+  set_init_in_progress_flag(__guard* g, int v)
+  { ((char *)g)[1] = v; }
 
-  static int
-  acquire (__guard *g)
+  static inline void
+  throw_recursive_init_exception()
   {
-    if (_GLIBCXX_GUARD_TEST (g))
-      return 0;
-
-    if (recursion_push (g))
-      {
 #ifdef __EXCEPTIONS
 	throw __gnu_cxx::recursive_init_error();
 #else
 	// Use __builtin_trap so we don't require abort().
-	__builtin_trap ();
+	__builtin_trap();
 #endif
-      }
+  }
+
+  // acuire() is a helper function used to acquire guard if thread support is
+  // not compiled in or is compiled in but not enabled at run-time.
+  static int
+  acquire(__guard *g)
+  {
+    // Quit if the object is already initialized.
+    if (_GLIBCXX_GUARD_TEST(g))
+      return 0;
+
+    if (init_in_progress_flag(g))
+	throw_recursive_init_exception();
+
+    set_init_in_progress_flag(g, 1);
     return 1;
   }
 
+  // Simple wrapper for exception safety.
+  struct mutex_wrapper
+  {
+#ifdef __GTHREADS
+    bool unlock;
+    mutex_wrapper() : unlock(true)
+    { get_static_mutex().lock(); }
+
+    ~mutex_wrapper()
+    {
+      if (unlock)
+	static_mutex->unlock();
+    }
+#endif
+  };
+
   extern "C"
   int __cxa_guard_acquire (__guard *g) 
   {
@@ -150,28 +225,39 @@
 
     if (__gthread_active_p ())
       {
-	// Simple wrapper for exception safety.
-	struct mutex_wrapper
-	{
-	  bool unlock;
-	  mutex_wrapper() : unlock(true)
-	  { get_static_mutex().lock(); }
-
-	  ~mutex_wrapper()
-	  {
-	    if (unlock)
-	      static_mutex->unlock();
-	  }
-	};
-
 	mutex_wrapper mw;
-	if (acquire (g))
+
+	while (1)	// When this loop is executing, mutex is locked.
 	  {
-	    mw.unlock = false;
-	    return 1;
+#ifdef __GTHREAD_HAS_COND
+	    // The static is allready initialized.
+	    if (_GLIBCXX_GUARD_TEST(g))
+	      return 0;	// The mutex will be unlocked via wrapper
+
+	    if (init_in_progress_flag(g))
+	      {
+		// The guarded static is currently being initialized by
+		// another thread, so we release mutex and wait for the
+		// conditional variable. We will lock the mutex again after
+		// this.
+		get_static_cond().wait_recursive(&get_static_mutex());
+	      }
+	    else
+	      {
+		set_init_in_progress_flag(g, 1);
+		return 1; // The mutex will be unlocked via wrapper.
+	      }
+#else
+	    // This provides compatibility with older systems not supporting
+	    // POSIX like conditional variables.
+	    if (acquire(g))
+	      {
+		mw.unlock = false;
+		return 1; // The mutex still locked.
+	      }
+	    return 0; // The mutex will be unlocked via wrapper.
+#endif
 	  }
-
-	return 0;
       }
 #endif
 
@@ -181,8 +267,24 @@
   extern "C"
   void __cxa_guard_abort (__guard *g)
   {
-    recursion_pop (g);
-#ifdef __GTHREADS
+#ifdef __GTHREAD_HAS_COND
+    if (__gthread_active_p())
+      {	
+	mutex_wrapper mw;
+
+	set_init_in_progress_flag(g, 0);
+
+	// If we abort, we still need to wake up all other threads waiting for
+	// the conditional variable.
+        get_static_cond().broadcast();
+	return;
+      }	
+#endif
+
+    set_init_in_progress_flag(g, 0);
+#if defined(__GTHREADS) && !defined(__GTHREAD_HAS_COND)
+    // This provides compatibility with older systems not supporting POSIX like
+    // conditional variables.
     if (__gthread_active_p ())
       static_mutex->unlock();
 #endif
@@ -191,10 +293,26 @@
   extern "C"
   void __cxa_guard_release (__guard *g)
   {
-    recursion_pop (g);
+#ifdef __GTHREAD_HAS_COND
+    if (__gthread_active_p())
+      {
+	mutex_wrapper mw;
+
+	set_init_in_progress_flag(g, 0);
+	_GLIBCXX_GUARD_SET_AND_RELEASE(g);
+
+        get_static_cond().broadcast();
+	return;
+      }	
+#endif
+
+    set_init_in_progress_flag(g, 0);
     _GLIBCXX_GUARD_SET_AND_RELEASE (g);
-#ifdef __GTHREADS
-    if (__gthread_active_p ())
+
+#if defined(__GTHREADS) && !defined(__GTHREAD_HAS_COND)
+    // This provides compatibility with older systems not supporting POSIX like
+    // conditional variables.
+    if (__gthread_active_p())
       static_mutex->unlock();
 #endif
   }
diff -Nru gcc-old/gcc/libstdc++-v3/testsuite/thread/guard.cc gcc-new/gcc/libstdc++-v3/testsuite/thread/guard.cc
--- gcc-old/gcc/libstdc++-v3/testsuite/thread/guard.cc	1969-12-31 16:00:00.000000000 -0800
+++ gcc-new/gcc/libstdc++-v3/testsuite/thread/guard.cc	2007-09-18 13:19:01.000000000 -0700
@@ -0,0 +1,67 @@
+//
+// Copyright (C) 2007 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// { dg-do run { target *-*-freebsd* *-*-netbsd* *-*-linux* *-*-solaris* *-*-cygwin *-*-darwin* alpha*-*-osf* } }
+// { dg-options "-pthread" { target *-*-freebsd* *-*-netbsd* *-*-linux* *-*-solaris* *-*-darwin* alpha*-*-osf* } }
+
+#include <cstdlib>
+#include <pthread.h>
+
+// This used to deadlock with the old libstdc++ because there is only one
+// global mutex guarding initialization of statics and it is held during by
+// the initializer thread of a static until the variable is completely
+// initialized. If the initializer thread creates and waits for another thread
+// which also initializes a static variable, there will be a deadlock because
+// the first thread is holding the mutex and waiting for the second thread,
+// which is blocked when it is acquiring the mutex.
+
+int
+get_bar (void)
+{
+  return 1;
+}
+
+void*
+do_something (void *arg)
+{
+  static int bar = get_bar ();
+  return NULL;
+}
+
+int
+get_foo (void)
+{
+  int status;
+  pthread_t new_thread;
+
+  if (pthread_create (&new_thread, NULL, do_something, NULL) != 0)
+    std::abort ();
+
+  if (pthread_join (new_thread, NULL) != 0)
+    std::abort ();
+
+  return 1;
+}
+
+int
+main (int argc, char **argv)
+{
+  static int foo = get_foo ();
+  return 0;  
+}

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Jason Merrill]

Eric Botcazou wrote:
>> 2007-09-13  Doug Kwan  <dougkwan@google.com>
>>
>>         * gcc/gthr-posix.h (__gthread_cond_broadcast, __gthread_cond_wait,
>>           __gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
>>           Add to extend interface for POSIX conditional variables.
>>           (__GTHREAD_HAS_COND): Macro defined to signify support of
>>           conditional variables.
> 
> Is this supported by POSIX 95?  If so, gthr-posix95.h should be updated too.

The condition variable stuff is part of 1003.1c-1995, yes.  I assume 
that's what you mean by POSIX 95.  You should be able to just apply the 
same changes to gthr-posix95.h.

> !               get_static_cond().wait_recursive(&get_static_mutex());

Not a big deal, but you should be able to just use 
wait_recursive(static_mutex) here.  Whichever you prefer.

The patch is OK with the update to gthr-posix95.h; I imagine Eric will 
let you know if it breaks for some reason.

Jason

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Doug Kwan (關振德)]

Hi Jason,

2007/9/20, Jason Merrill <jason@redhat.com>:

> The patch is OK with the update to gthr-posix95.h; I imagine Eric will
> let you know if it breaks for some reason.

Does that mena it is OK to check that in? I don't have write access to
the gcc SVN repository and I need someone to do that for me.

Thanks

-Doug

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Benjamin Kosnik]

> Does that mena it is OK to check that in? 

Yes.

> I don't have write access to
> the gcc SVN repository and I need someone to do that for me.

I'll check it in for you if you do the updates to gthr-95, as
requested by jason, and post the new patch.

Let's get this in folks.

best,
benjamin

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Paolo Carlini]

Benjamin Kosnik wrote:

>Let's get this in folks.
>  
>
I agree, 100%. That said, only to better understand the issue, I'd like 
to see a minimum of discussion about the binary compatibility issues: is 
it guaranteed that it will be possible to link an object build with the 
current headers to another built with the new headers and obtain an 
overall behavior no worse than the current one? In the remote case that 
this is not true, I'm ok anyway with the patch, but that should be clear 
to all the interested people and in case a note added to the 
documentation about that.

Thanks,
Paolo.

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Doug Kwan (關振德)]

Hi Benjamin,

    The patch in the previous mail on 9/18 has the gthr-posix95.h already.

-Doug


2007/10/3, Benjamin Kosnik <bkoz@redhat.com>:
>
> > Does that mena it is OK to check that in?
>
> Yes.
>
> > I don't have write access to
> > the gcc SVN repository and I need someone to do that for me.
>
> I'll check it in for you if you do the updates to gthr-95, as
> requested by jason, and post the new patch.
>
> Let's get this in folks.
>
> best,
> benjamin
>

Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Jason Merrill]

Doug Kwan (關振德) wrote:
>     The patch in the previous mail on 9/18 has the gthr-posix95.h already.

Ah, I didn't see your 9/18 mail.  I've applied the patch, thanks a lot.

Jason

Build error with Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Hans-Peter Nilsson]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3416 bytes --]

On Mon, 17 Sep 2007, Doug Kwan (Ãö®¶¼w) wrote:
> Hi Jason,
>
>   Here is the patch without the skip-list.
>
> -Doug
>
> -----
> 2007-09-13  Doug Kwan  <dougkwan@google.com>
>
>        * gcc/gthr-posix.h (__gthread_cond_broadcast, __gthread_cond_wait,
>          __gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
>          Add to extend interface for POSIX conditional variables.
>          (__GTHREAD_HAS_COND): Macro defined to signify support of
>          conditional variables.
>        Likewise
>        * gcc/gthr-single.h (__gthread_cond_broadcast, __gthread_cond_wait,
>          __gthread_cond_wait_recursive, __gthread_self, __gthread_equal):
>          Add to extend interface for POSIX conditional variables.
...

A patch in the range 129024:129030, i.e. this one, caused the 
following build failure for cris-elf (cutnpasted with wrap):

In file included from 
/tmp/hpautotest-gcc1/gcc/libgcc/../gcc/gthr.h:136,
                  from 
/tmp/hpautotest-gcc1/gcc/libgcc/../gcc/unwind-dw2.c:42:
/tmp/hpautotest-gcc1/gcc/libgcc/../gcc/gthr-single.h:255: error: 
expected ')' before 'cond'
/tmp/hpautotest-gcc1/gcc/libgcc/../gcc/gthr-single.h:261: error: 
expected ')' before 'cond'
/tmp/hpautotest-gcc1/gcc/libgcc/../gcc/gthr-single.h:267: error: 
expected ')' before 'cond'

coming from:
Index: gcc/gthr-single.h
===================================================================
--- gcc/gthr-single.h	(revision 129024)
+++ gcc/gthr-single.h	(revision 129030)
@@ -251,6 +251,25 @@ __gthread_recursive_mutex_unlock (__gthr
    return __gthread_mutex_unlock (mutex);
  }

+static inline int
+__gthread_cond_broadcast (__gthread_cond_t cond)
+{
+  return 0;
+}
+
+static inline int
+__gthread_cond_wait (__gthread_cond_t cond, __gthread_mutex_t *mutex)
+{
+  return 0;
+}
+
+static inline int
+__gthread_cond_wait_recursive (__gthread_cond_t cond,
+			       __gthread_recursive_mutex_t *mutex)
+{
+  return 0;
+}
+
  #endif /* _LIBOBJC */

  #undef UNUSED

(Immediate cause being lack of __gthread_cond_t type.  Tsk tsk, 
totally untested.)

At first I thought the correct change would be to add "typedef 
int __gthread_cond_t;" to gthr-single.h, but when I looked 
deeper, reading gthr.h and the patch, it seemed like these 
functions and the __gthread_cond_t type would be unused without 
a "#define __GTHREAD_HAS_COND 1".  Inspection of the 
libstdc++-v3 users of the macro (libsupc++/guard.cc and 
include/ext/concurrence.h) support the documentation.

Now, I argue that reverting the part of the patch above (to 
gthr-single.h) is the obviously correct choice (it solves the 
problem with no regressions from 129024 for cris-elf), but David 
Edelsohn disagrees, being on the typedef side.  Hence, I can't 
safely argue that reverting the patch is the obvious choice.

I mean, having unused, uncalled stubs, does seem wrong.  Those 
functions and the type are optional, and gthr-single.h doesn't 
define the macro saying the option is active.

You might think, why not add the "#define __GTHREAD_HAS_COND 1" 
to gthr-single.h too?  Well, because then gthr-single.h would 
say we have optional functionality that we just have stubs for. 
It'd also mean that all users have the macro, and we could just 
remove that macro. That doesn't seem to be what was intended.

Please advise.

brgds, H-P

Re: Build error with Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Jason Merrill]

Since uses are controlled with the __GTHREAD_HAS_COND macro, I would be 
inclined to just remove those functions from gthr-single.h.

Jason

Re: Build error with Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Hans-Peter Nilsson]

On Fri, 5 Oct 2007, Jason Merrill wrote:
> Since uses are controlled with the __GTHREAD_HAS_COND macro, I would be 
> inclined to just remove those functions from gthr-single.h.

Done.

(FWIW, for the record, I missed that there are plenty of other 
gthr-*.h than those affected by the patch, so please ignore the 
"It'd also mean that all users have the macro" part.)

brgds, H-P

Re: Build error with Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Doug Kwan (關振德)]

Sorry about that. Yes, remove these from gthr-single.h should be fine.
The code has been tested on Linux only as I don't have access to
system using other thread models in gcc.

-Doug

2007/10/5, Jason Merrill <jason@redhat.com>:
> Since uses are controlled with the __GTHREAD_HAS_COND macro, I would be
> inclined to just remove those functions from gthr-single.h.
>
> Jason
>

Re: Build error with Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Hans-Peter Nilsson]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 361 bytes --]

On Sun, 7 Oct 2007, Doug Kwan (Ãö®¶¼w) wrote:
> The code has been tested on Linux only as I don't have access to
> system using other thread models in gcc.

Sorry if you're already aware, but that's trigging my knee-jerk 
reply: everybody (well, at least all on Linux-hosted systems) 
has access to simulator targets, see simtest-howto.html.

brgds, H-P

Re: Build error with Re: ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++

[Andrew Pinski]

On 10/7/07, Doug Kwan (關振德) <dougkwan@google.com> wrote:
> Sorry about that. Yes, remove these from gthr-single.h should be fine.
> The code has been tested on Linux only as I don't have access to
> system using other thread models in gcc.

You have access to the single threading model under GNU/Linux, use
--with-threads=single .

-- Pinski