public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++
@ 2007-08-02 20:56 Doug Kwan (關振德)
  2007-08-15 21:54 ` Jason Merrill
  0 siblings, 1 reply; 20+ messages in thread
From: Doug Kwan (關振德) @ 2007-08-02 20:56 UTC (permalink / raw)
  To: gcc-patches, libstdc++

[-- 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;  
+}

^ permalink raw reply	[flat|nested] 20+ messages in thread
end of thread, other threads:[~2007-10-07 20:41 UTC | newest]

Thread overview: 20+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-08-02 20:56 ping [PATCH] Fix a deadlock bug in static variable initialization in libsupc++ Doug Kwan (關振德)
2007-08-15 21:54 ` Jason Merrill
2007-08-16  5:38   ` Doug Kwan (關振德)
2007-08-16 18:55     ` Jason Merrill
2007-09-17 23:30   ` Doug Kwan (關振德)
2007-09-18  7:19     ` Eric Botcazou
2007-09-18  8:43       ` Doug Kwan (關振德)
2007-09-20 20:01       ` Jason Merrill
2007-10-03 21:56         ` Doug Kwan (關振德)
2007-10-03 22:08           ` Benjamin Kosnik
2007-10-03 22:24             ` Paolo Carlini
2007-10-04  0:20             ` Doug Kwan (關振德)
2007-10-05  5:41               ` Jason Merrill
     [not found]     ` <m3y7f49goe.fsf@fleche.redhat.com>
2007-09-18 22:52       ` Doug Kwan (關振德)
2007-10-05 21:18     ` Build error with " Hans-Peter Nilsson
2007-10-05 21:44       ` Jason Merrill
2007-10-05 22:21         ` Hans-Peter Nilsson
2007-10-07 17:51         ` Doug Kwan (關振德)
2007-10-07 19:32           ` Hans-Peter Nilsson
2007-10-07 20:41           ` Andrew Pinski

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).