Counter-PATCH (libstdc++-v3, mainline) for: std::_Atomic_swap for i386

[Loren James Rittle <rittle at latour dot rsch dot comm dot mot dot com>]

Danny R. Smith writes:

> Recent builds of libstdc++ on mingw (__GTHREAD_MUTEX_INIT not defined)
> gives this.

[...]
> make[2]: *** [ext-inst.lo] Error 1

Yup, if I delete the _Atomic_swap implementation entirely from
include/bits/stl_threads.h and touch src/ext-inst.cc; mainline fails
to rebuild for me on i386-unknown-freebsd4.8 whereas it still rebuilds
fine on 3.3.  Perhaps, related to further tightening/correctness of
template processing?

> The following patch, based on the recent discussion of i386
> __exchange_and_add, fixes.

Your patch would be approved, but read on for why I propose a counter
patch... ;-)   _Atomic_swap is defined:

./include/bits/stl_threads.h

and used in precisely one place inside:

./include/ext/ropeimpl.h

Since I've been involved with libstdc++-v3, ext/rope's special use of
_Atomic_swap has been a non-portable pain in the rump (as we received
the code it supported ~2 cpu models and/or pthread mutex).  If
something did change, then this will affect more ports than just i386
without __GTHREAD_MUTEX_INIT (e.g. at a minimum, some versions of
HP-UX as well, I'd guess).

In any event, I'd much rather see us recode the race below to base it
on __exchange_and_add directly (as the basic_string<> implementation
uses) or a proper gthr mutex and then axe _Atomic_swap's use entirely:

    __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
    if (0 != __old_c_string) return(__old_c_string);
    size_t __s = size();
    _CharT* __result = _Data_allocate(__s + 1);
    _S_flatten(this->_M_tree_ptr, __result);
    __result[__s] = _S_eos((_CharT*)0);
#   ifdef __GC
        _M_tree_ptr->_M_c_string = __result;
#   else
      if ((__old_c_string = (__GC_CONST _CharT*)
             std::_Atomic_swap((unsigned long *)
                               (&(this->_M_tree_ptr->_M_c_string)),
                          (unsigned long)__result)) != 0) {
        // It must have been added in the interim.  Hence it had to have been
        // separately allocated.  Deallocate the old copy, since we just
        // replaced it.
        _Destroy(__old_c_string, __old_c_string + __s + 1);
        _Data_deallocate(__old_c_string, __s + 1);
      }
#   endif
    return(__result);

BTW, I think there is an MT bug in the above use of _Atomic_swap
anyway (yup, there is, add an explicit yield point right before __s is
initialized and run an MT test case which uses rope in a complex
enough manner such that c_str calculation is deferred).  If one
atomicly swaps pointers only to delete the copy found in place of the
one we just built and installed, then we've just killed a previous
value returned from c_str() to the application (or about to be
returned by another thread)...

IMHO, a proper sequence of MT-safe code might look like:

//if !__GC, OBTAIN MUTEX/LOCK
    __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
    if (0 == __result)
      {
        size_t __s = size();
        __result = _Data_allocate(__s + 1);
        _S_flatten(this->_M_tree_ptr, __result);
        __result[__s] = _S_eos((_CharT*)0);
        this->_M_tree_ptr->_M_c_string = __result;
      }
//if !__GC, RELEASE MUTEX/LOCK
    return(__result);

Danny, here is the counter-patch (which I did test against both mutex
init styles).  I shall commit to mainline after you verify that it
works for you in your environment and you agree that it is not a
completely disagreeable replacement patch (along with a new threaded
test case which actually tests c_str in a mode where an internal
failure could result):

	* include/bits/stl_threads.h (_Atomic_swap): Kill it...
	(_Swap_lock_struct<>): ...and the horse it rode in on.
	* src/globals.cc (_Swap_lock_struct<>): Likewise.
	* include/ext/stl_rope.h (_Rope_RopeRep<>::_M_c_string_lock): New
	member to support...
	* include/ext/ropeimpl.h (rope<>::c_str): Follow *all* memory
	visibility rules related to POSIX threads.
	* testsuite/thread/pthread7-rope.cc: New test.

Index: include/bits/stl_threads.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_threads.h,v
retrieving revision 1.14
diff -c -r1.14 stl_threads.h
*** include/bits/stl_threads.h	13 Oct 2002 06:35:15 -0000	1.14
--- include/bits/stl_threads.h	3 May 2003 10:12:15 -0000
***************
*** 97,131 ****
        return __tmp;
      }
    };
- 
-   // Atomic swap on unsigned long
-   // This is guaranteed to behave as though it were atomic only if all
-   // possibly concurrent updates use _Atomic_swap.
-   // In some cases the operation is emulated with a lock.
- #if defined (__GTHREAD_MUTEX_INIT)
-   // This could be optimized to use the atomicity.h abstraction layer.
-   // vyzo: simple _Atomic_swap implementation following the guidelines above
-   // We use a template here only to get a unique initialized instance.
-   template<int __dummy>
-     struct _Swap_lock_struct 
-     { static __gthread_mutex_t _S_swap_lock; };
- 
-   template<int __dummy>
-     __gthread_mutex_t
-     _Swap_lock_struct<__dummy>::_S_swap_lock = __GTHREAD_MUTEX_INIT;
- 
-   // This should be portable, but performance is expected to be quite
-   // awful.  This really needs platform specific code.
-   inline unsigned long 
-   _Atomic_swap(unsigned long * __p, unsigned long __q) 
-   {
-     __gthread_mutex_lock(&_Swap_lock_struct<0>::_S_swap_lock);
-     unsigned long __result = *__p;
-     *__p = __q;
-     __gthread_mutex_unlock(&_Swap_lock_struct<0>::_S_swap_lock);
-     return __result;
-   }
- #endif
  } //namespace std
  
    // Locking class.  Note that this class *does not have a
--- 97,102 ----
Index: src/globals.cc
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/src/globals.cc,v
retrieving revision 1.15
diff -c -r1.15 globals.cc
*** src/globals.cc	28 Apr 2003 03:41:49 -0000	1.15
--- src/globals.cc	3 May 2003 10:12:15 -0000
***************
*** 227,235 ****
    // allows static initialization of these objects on systems that need a
    // function call to initialize a mutex.  For example, see stl_threads.h.
  #ifdef __GTHREAD_MUTEX_INIT
-   // Need to provide explicit instantiations of static data for
-   // systems with broken weak linkage support.
-   template __gthread_mutex_t _Swap_lock_struct<0>::_S_swap_lock;
  #elif defined(__GTHREAD_MUTEX_INIT_FUNCTION)
    __gthread_once_t _GLIBCPP_once = __GTHREAD_ONCE_INIT;
    __gthread_mutex_t _GLIBCPP_mutex;
--- 227,232 ----
Index: include/ext/stl_rope.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/ext/stl_rope.h,v
retrieving revision 1.19
diff -c -r1.19 stl_rope.h
*** include/ext/stl_rope.h	16 Jan 2003 20:30:26 -0000	1.19
--- include/ext/stl_rope.h	3 May 2003 10:12:15 -0000
***************
*** 483,488 ****
--- 483,489 ----
      bool _M_is_balanced:8;
      unsigned char _M_depth;
      __GC_CONST _CharT* _M_c_string;
+     __gthread_mutex_t _M_c_string_lock;
                          /* Flattened version of string, if needed.  */
                          /* typically 0.                             */
                          /* If it's not 0, then the memory is owned  */
***************
*** 498,504 ****
--- 499,510 ----
            _Refcount_Base(1),
  #         endif
            _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
+ #ifdef __GTHREAD_MUTEX_INIT
+ 	  , _M_c_string_lock (__GTHREAD_MUTEX_INIT)
      { }
+ #else
+     { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
+ #endif
  #   ifdef __GC
          void _M_incr () {}
  #   endif
Index: include/ext/ropeimpl.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/ext/ropeimpl.h,v
retrieving revision 1.18
diff -c -r1.18 ropeimpl.h
*** include/ext/ropeimpl.h	28 Apr 2003 23:05:57 -0000	1.18
--- include/ext/ropeimpl.h	3 May 2003 10:12:15 -0000
***************
*** 1450,1475 ****
  					     // but probably fast.
          return _S_empty_c_str;
      }
!     __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
!     if (0 != __old_c_string) return(__old_c_string);
!     size_t __s = size();
!     _CharT* __result = _Data_allocate(__s + 1);
!     _S_flatten(this->_M_tree_ptr, __result);
!     __result[__s] = _S_eos((_CharT*)0);
! #   ifdef __GC
! 	_M_tree_ptr->_M_c_string = __result;
! #   else
!       if ((__old_c_string = (__GC_CONST _CharT*)
!              std::_Atomic_swap((unsigned long *)
! 			       (&(this->_M_tree_ptr->_M_c_string)),
! 			  (unsigned long)__result)) != 0) {
! 	// It must have been added in the interim.  Hence it had to have been
! 	// separately allocated.  Deallocate the old copy, since we just
! 	// replaced it.
! 	_Destroy(__old_c_string, __old_c_string + __s + 1);
! 	_Data_deallocate(__old_c_string, __s + 1);
        }
! #   endif
      return(__result);
  }
  
--- 1450,1466 ----
  					     // but probably fast.
          return _S_empty_c_str;
      }
!     __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
!     __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
!     if (0 == __result)
!       {
! 	size_t __s = size();
! 	__result = _Data_allocate(__s + 1);
! 	_S_flatten(this->_M_tree_ptr, __result);
! 	__result[__s] = _S_eos((_CharT*)0);
! 	this->_M_tree_ptr->_M_c_string = __result;
        }
!     __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
      return(__result);
  }
  
Index: testsuite/thread/pthread7-rope.cc
===================================================================
RCS file: testsuite/thread/pthread7-rope.cc
diff -N testsuite/thread/pthread7-rope.cc
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- testsuite/thread/pthread7-rope.cc	3 May 2003 10:12:15 -0000
***************
*** 0 ****
--- 1,106 ----
+ // 2003-05-03  Loren J. Rittle <rittle@labs.mot.com> <ljrittle@acm.org>
+ //
+ // Copyright (C) 2003 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ // USA.
+ 
+ // { dg-do run { target *-*-freebsd* *-*-netbsd* *-*-linux* *-*-solaris* *-*-cygwin *-*-darwin* } }
+ // { dg-options "-DDEBUG_ASSERT -pthread" { target *-*-freebsd* *-*-netbsd* *-*-linux* } }
+ // { dg-options "-DDEBUG_ASSERT -pthreads" { target *-*-solaris* } }
+ 
+ #include <ext/rope>
+ #include <cstring>
+ #include <testsuite_hooks.h>
+ 
+ // Do not include <pthread.h> explicitly; if threads are properly
+ // configured for the port, then it is picked up free from STL headers.
+ 
+ #if __GTHREADS
+ 
+ const int max_thread_count = 4;
+ const int max_loop_count = 10000;
+ 
+ __gnu_cxx::crope foo4;
+ 
+ void* thread_main (void *)
+ {
+   // To see a problem with gcc 3.3 and before, set a break point here.
+   // Single step through c_str implementation, call sched_yield after
+   // capture of NULL __old_c_string in any thread.  Single step
+   // through another thread past that same point.  Now, one thread
+   // will receive a bad pointer return.  Adding dummy sched_yield
+   // should never change program semantics under POSIX threads.
+   const char* data4 = foo4.c_str();
+ 
+   // Please note that the memory leak in the rope implementation with
+   // this test case, existed before and after fixing this bug...
+ 
+   VERIFY( !std::strcmp (data4, "barbazbonglehellohellohello") );
+ }
+ 
+ int
+ main()
+ {
+   pthread_t tid[max_thread_count];
+ 
+ #if defined(__sun) && defined(__svr4__)
+   pthread_setconcurrency (max_thread_count);
+ #endif
+ 
+   __gnu_cxx::crope foo;
+   foo += "bar";
+   foo += "baz";
+   foo += "bongle";
+   const char* data = foo.c_str();
+   VERIFY( !std::strcmp (data, "barbazbongle") );
+ 
+   const char* data2;
+   {
+     __gnu_cxx::crope foo2;
+     foo2 += "bar2";
+     foo2 += "baz2";
+     foo2 += "bongle2";
+     data2 = foo2.c_str();
+     VERIFY( !std::strcmp (data2, "bar2baz2bongle2") );
+   }
+ 
+   __gnu_cxx::crope foo3 ("hello");
+   const char* data3 = foo3.c_str();
+   VERIFY( !std::strcmp (data3, "hello") );
+ 
+   for (int j = 0; j < max_loop_count; j++)
+     {
+       foo4 = foo;
+       foo4 += foo3;
+       foo4 += foo3;
+       foo4 += foo3;
+ 
+       for (int i = 0; i < max_thread_count; i++)
+ 	pthread_create (&tid[i], NULL, thread_main, 0);
+ 
+       for (int i = 0; i < max_thread_count; i++)
+ 	pthread_join (tid[i], NULL);
+     }
+ 
+   // Nothing says the data will be trashed at this point...
+   VERIFY( std::strcmp (data2, "bar2baz2bongle2") );
+ 
+   return 0;
+ }
+ #else
+ int main (void) {}
+ #endif