[Bug libstdc++/62313] Data race in debug iterators

[Bug libstdc++/62313] Data race in debug iterators

[François Dumont]

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

Hi

     Here is a proposal to fix this data race issue.

     I finally generalized bitset approach to fix it by inheriting from 
the normal iterator first and then the _Safe_iterator_base type. None of 
the libstdc++ iterator types are final so it is fine. Surprisingly, 
despite inheritance being private gcc got confused between 
_Safe_iterator_base _M_next and forward_list _M_next so I need to adapt 
some code to make usage of _Safe_iterator_base _M_next explicit.

     I also consider any operator where normal iterator is being 
modified while the safe iterator is linked to the list of iterators. 
This is necessary to make sure that thread sanatizer won't consider a 
race condition. I didn't touch to bitset::reference because list 
references are only access on bitset destruction which is clearly not an 
operation allowed to do while playing with references in another thread.

     Do you see any way to check for this problem in the testsuite ? Is 
there a thread sanitizer we could use ?

2014-09-10  François Dumont  <fdumont@gcc.gnu.org>

     PR libstdc++/62313
     * include/debug/safe_base.h
     (_Safe_iterator_base(const _Safe_iterator_base&)): Delete declaration.
     (_Safe_iterator_base& operator=(const _Safe_iterator_base&)): Likewise.
     * include/debug/safe_iterator.h (_Safe_iterator<>): Move normal 
iterator
     before _Safe_iterator_base in memory. Lock before modifying the 
iterator
     in numerous places.
     * include/debug/safe_local_iterator.h
     (_Safe_local_iterator_base(const _Safe_local_iterator_base&)): Delete
     declaration.
     (_Safe_local_iterator_base& operator=(const 
_Safe_local_iterator_base&)):
     Likewise.
     * include/debug/safe_unordered_base.h (_Safe_local_iterator<>):  Move
     normal iterator before _Safe_iterator_base in memory. Lock before
     modifying the iterator in numerous places.
     * include/debug/forward_list (_Safe_forward_list<>::_M_swap_aux): 
Adapt.
     * include/debug/safe_sequence.tcc
     (_Safe_sequence<>::_M_transfer_from_if): Adapt.

Tested under Linux x86_64 debug mode.

Ok to commit ?

François

[-- Attachment #2: debug.patch --]
[-- Type: text/x-patch, Size: 23683 bytes --]

Index: include/debug/forward_list
===================================================================
--- include/debug/forward_list	(revision 215134)
+++ include/debug/forward_list	(working copy)
@@ -86,24 +86,26 @@
       for (_Safe_iterator_base* __iter = __lhs_iterators; __iter;)
 	{
 	  // Even iterator is cast to const_iterator, not a problem.
-	  const_iterator* __victim = static_cast<const_iterator*>(__iter);
+	  _Safe_iterator_base* __victim_base = __iter;
+	  const_iterator* __victim =
+	    static_cast<const_iterator*>(__victim_base);
 	  __iter = __iter->_M_next;
 	  if (__victim->base() == __rseq._M_base().cbefore_begin())
 	    {
 	      __victim->_M_unlink();
-	      if (__lhs_iterators == __victim)
-		__lhs_iterators = __victim->_M_next;
+	      if (__lhs_iterators == __victim_base)
+		__lhs_iterators = __victim_base->_M_next;
 	      if (__bbegin_its)
 		{
-		  __victim->_M_next = __bbegin_its;
-		  __bbegin_its->_M_prior = __victim;
+		  __victim_base->_M_next = __bbegin_its;
+		  __bbegin_its->_M_prior = __victim_base;
 		}
 	      else
-		__last_bbegin = __victim;
-	      __bbegin_its = __victim;
+		__last_bbegin = __victim_base;
+	      __bbegin_its = __victim_base;
 	    }
 	  else
-	    __victim->_M_sequence = &__lhs;
+	    __victim_base->_M_sequence = &__lhs;
 	}
 
       if (__bbegin_its)
Index: include/debug/safe_base.h
===================================================================
--- include/debug/safe_base.h	(revision 215134)
+++ include/debug/safe_base.h	(working copy)
@@ -95,12 +95,6 @@
     : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
     { this->_M_attach(__x._M_sequence, __constant); }
 
-    _Safe_iterator_base&
-    operator=(const _Safe_iterator_base&);
-
-    explicit
-    _Safe_iterator_base(const _Safe_iterator_base&);
-
     ~_Safe_iterator_base() { this->_M_detach(); }
 
     /** For use in _Safe_iterator. */
Index: include/debug/safe_iterator.h
===================================================================
--- include/debug/safe_iterator.h	(revision 215134)
+++ include/debug/safe_iterator.h	(working copy)
@@ -109,16 +109,21 @@
    *  %_Safe_iterator has member functions for iterator invalidation,
    *  attaching/detaching the iterator from sequences, and querying
    *  the iterator's state.
+   *
+   *  Note that _Iterator must rely first in the type memory layout so that it
+   *  gets initialized before the iterator is being attached to the container
+   *  list of iterators and it is being dettached before _Iterator get
+   *  destroy. Otherwise it would result in a data race.
    */
   template<typename _Iterator, typename _Sequence>
-    class _Safe_iterator : public _Safe_iterator_base
+    class _Safe_iterator
+    : private _Iterator,
+      public _Safe_iterator_base
     {
-      typedef _Safe_iterator _Self;
+      typedef _Iterator _Ite_base;
+      typedef _Safe_iterator_base _Safe_base;
       typedef typename _Sequence::const_iterator _Const_iterator;
 
-      /// The underlying iterator
-      _Iterator _M_current;
-
       /// Determine if this is a constant iterator.
       bool
       _M_constant() const
@@ -126,6 +131,15 @@
 
       typedef std::iterator_traits<_Iterator> _Traits;
 
+      struct _Attach_single
+      { };
+
+      _Safe_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
+		     _Attach_single)
+      _GLIBCXX_NOEXCEPT
+      : _Ite_base(__i)
+      { _M_attach_single(__seq); }
+
     public:
       typedef _Iterator					iterator_type;
       typedef typename _Traits::iterator_category	iterator_category;
@@ -135,7 +149,7 @@
       typedef typename _Traits::pointer			pointer;
 
       /// @post the iterator is singular and unattached
-      _Safe_iterator() _GLIBCXX_NOEXCEPT : _M_current() { }
+      _Safe_iterator() _GLIBCXX_NOEXCEPT : _Ite_base() { }
 
       /**
        * @brief Safe iterator construction from an unsafe iterator and
@@ -144,11 +158,11 @@
        * @pre @p seq is not NULL
        * @post this is not singular
        */
-      _Safe_iterator(const _Iterator& __i, const _Sequence* __seq)
+      _Safe_iterator(const _Iterator& __i, const _Safe_sequence_base* __seq)
       _GLIBCXX_NOEXCEPT
-      : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i)
+      : _Ite_base(__i), _Safe_base(__seq, _M_constant())
       {
-	_GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+	_GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
 			      _M_message(__msg_init_singular)
 			      ._M_iterator(*this, "this"));
       }
@@ -157,15 +171,16 @@
        * @brief Copy construction.
        */
       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
-      : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current)
+      : _Ite_base(__x.base())
       {
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// DR 408. Is vector<reverse_iterator<char*> > forbidden?
 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
-			      || __x._M_current == _Iterator(),
+			      || __x.base() == _Iterator(),
 			      _M_message(__msg_init_copy_singular)
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
+	_M_attach(__x._M_sequence);
       }
 
 #if __cplusplus >= 201103L
@@ -173,16 +188,18 @@
        * @brief Move construction.
        * @post __x is singular and unattached
        */
-      _Safe_iterator(_Safe_iterator&& __x) noexcept : _M_current()
+      _Safe_iterator(_Safe_iterator&& __x) noexcept
+      : _Ite_base()
       {
 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
-			      || __x._M_current == _Iterator(),
+			      || __x.base() == _Iterator(),
 			      _M_message(__msg_init_copy_singular)
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
-	std::swap(_M_current, __x._M_current);
-	this->_M_attach(__x._M_sequence);
+	_Safe_sequence_base* __seq = __x._M_sequence;
 	__x._M_detach();
+	std::swap(base(), __x.base());
+	_M_attach(__seq);
       }
 #endif
 
@@ -196,7 +213,7 @@
 	  typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
 		      typename _Sequence::iterator::iterator_type>::__value),
 		   _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
-	: _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base())
+	: _Ite_base(__x.base())
 	{
 	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
 	  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
@@ -205,6 +222,7 @@
 				_M_message(__msg_init_const_singular)
 				._M_iterator(*this, "this")
 				._M_iterator(__x, "other"));
+	  _M_attach(__x._M_sequence);
 	}
 
       /**
@@ -216,12 +234,24 @@
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// DR 408. Is vector<reverse_iterator<char*> > forbidden?
 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
-			      || __x._M_current == _Iterator(),
+			      || __x.base() == _Iterator(),
 			      _M_message(__msg_copy_singular)
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
-	_M_current = __x._M_current;
-	this->_M_attach(__x._M_sequence);
+
+	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
+	  {
+	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	    base() = __x.base();
+	    _M_version = __x._M_sequence->_M_version;
+	  }
+	else
+	  {
+	    _M_detach();
+	    base() = __x.base();
+	    _M_attach(__x._M_sequence);
+	  }
+
 	return *this;
       }
 
@@ -237,14 +267,26 @@
 			      _M_message(__msg_self_move_assign)
 			      ._M_iterator(*this, "this"));
 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
-			      || __x._M_current == _Iterator(),
+			      || __x.base() == _Iterator(),
 			      _M_message(__msg_copy_singular)
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
-	_M_current = __x._M_current;
-	_M_attach(__x._M_sequence);
+
+	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
+	  {
+	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	    base() = __x.base();
+	    _M_version = __x._M_sequence->_M_version;
+	  }
+	else
+	  {
+	    _M_detach();
+	    base() = __x.base();
+	    _M_attach(__x._M_sequence);
+	  }
+
 	__x._M_detach();
-	__x._M_current = _Iterator();
+	__x.base() = _Iterator();
 	return *this;
       }
 #endif
@@ -259,7 +301,7 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 			      _M_message(__msg_bad_deref)
 			      ._M_iterator(*this, "this"));
-	return *_M_current;
+	return *base();
       }
 
       /**
@@ -273,7 +315,7 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 			      _M_message(__msg_bad_deref)
 			      ._M_iterator(*this, "this"));
-	return std::__addressof(*_M_current);
+	return std::__addressof(*base());
       }
 
       // ------ Input iterator requirements ------
@@ -287,7 +329,8 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
-	++_M_current;
+	__gnu_cxx::__scoped_lock(this->_M_get_mutex());
+	++base();
 	return *this;
       }
 
@@ -301,9 +344,8 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
-	_Safe_iterator __tmp(*this);
-	++_M_current;
-	return __tmp;
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
       }
 
       // ------ Bidirectional iterator requirements ------
@@ -317,7 +359,8 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 			      _M_message(__msg_bad_dec)
 			      ._M_iterator(*this, "this"));
-	--_M_current;
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	--base();
 	return *this;
       }
 
@@ -331,9 +374,8 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 			      _M_message(__msg_bad_dec)
 			      ._M_iterator(*this, "this"));
-	_Safe_iterator __tmp(*this);
-	--_M_current;
-	return __tmp;
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
       }
 
       // ------ Random access iterator requirements ------
@@ -344,8 +386,7 @@
 			      && this->_M_can_advance(__n+1),
 			      _M_message(__msg_iter_subscript_oob)
 			      ._M_iterator(*this)._M_integer(__n));
-
-	return _M_current[__n];
+	return base()[__n];
       }
 
       _Safe_iterator&
@@ -354,7 +395,8 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 			      _M_message(__msg_advance_oob)
 			      ._M_iterator(*this)._M_integer(__n));
-	_M_current += __n;
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	base() += __n;
 	return *this;
       }
 
@@ -361,9 +403,10 @@
       _Safe_iterator
       operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
       {
-	_Safe_iterator __tmp(*this);
-	__tmp += __n;
-	return __tmp;
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
+			      _M_message(__msg_advance_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	return _Safe_iterator(base() + __n, this->_M_sequence);
       }
 
       _Safe_iterator&
@@ -372,7 +415,8 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 			      _M_message(__msg_retreat_oob)
 			      ._M_iterator(*this)._M_integer(__n));
-	_M_current += -__n;
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	base() -= __n;
 	return *this;
       }
 
@@ -379,9 +423,10 @@
       _Safe_iterator
       operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
       {
-	_Safe_iterator __tmp(*this);
-	__tmp -= __n;
-	return __tmp;
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
+			      _M_message(__msg_retreat_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	return _Safe_iterator(base() - __n, this->_M_sequence);
       }
 
       // ------ Utilities ------
@@ -388,28 +433,27 @@
       /**
        * @brief Return the underlying iterator
        */
-      _Iterator
-      base() const _GLIBCXX_NOEXCEPT { return _M_current; }
+      _Iterator&
+      base() _GLIBCXX_NOEXCEPT { return *this; }
 
+      const _Iterator&
+      base() const _GLIBCXX_NOEXCEPT { return *this; }
+
       /**
        * @brief Conversion to underlying non-debug iterator to allow
        * better interaction with non-debug containers.
        */
-      operator _Iterator() const _GLIBCXX_NOEXCEPT { return _M_current; }
+      operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
 
       /** Attach iterator to the given sequence. */
       void
       _M_attach(_Safe_sequence_base* __seq)
-      {
-	_Safe_iterator_base::_M_attach(__seq, _M_constant());
-      }
+      { _Safe_base::_M_attach(__seq, _M_constant()); }
 
       /** Likewise, but not thread-safe. */
       void
       _M_attach_single(_Safe_sequence_base* __seq)
-      {
-	_Safe_iterator_base::_M_attach_single(__seq, _M_constant());
-      }
+      { _Safe_base::_M_attach_single(__seq, _M_constant()); }
 
       /// Is the iterator dereferenceable?
       bool
Index: include/debug/safe_local_iterator.h
===================================================================
--- include/debug/safe_local_iterator.h	(revision 215134)
+++ include/debug/safe_local_iterator.h	(working copy)
@@ -49,15 +49,15 @@
    *  the iterator's state.
    */
   template<typename _Iterator, typename _Sequence>
-    class _Safe_local_iterator : public _Safe_local_iterator_base
+    class _Safe_local_iterator
+    : private _Iterator
+    , public _Safe_local_iterator_base
     {
-      typedef _Safe_local_iterator _Self;
+      typedef _Iterator _Ite_base;
+      typedef _Safe_local_iterator_base _Safe_base;
       typedef typename _Sequence::const_local_iterator _Const_local_iterator;
       typedef typename _Sequence::size_type size_type;
 
-      /// The underlying iterator
-      _Iterator _M_current;
-
       /// Determine if this is a constant iterator.
       bool
       _M_constant() const
@@ -68,6 +68,14 @@
 
       typedef std::iterator_traits<_Iterator> _Traits;
 
+      struct _Attach_single
+      { };
+
+      _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont,
+			   _Attach_single) noexcept
+      : _Ite_base(__i)
+      { _M_attach_single(__cont); }
+
     public:
       typedef _Iterator					iterator_type;
       typedef typename _Traits::iterator_category	iterator_category;
@@ -77,7 +85,7 @@
       typedef typename _Traits::pointer			pointer;
 
       /// @post the iterator is singular and unattached
-      _Safe_local_iterator() : _M_current() { }
+      _Safe_local_iterator() noexcept : _Ite_base() { }
 
       /**
        * @brief Safe iterator construction from an unsafe iterator and
@@ -86,8 +94,9 @@
        * @pre @p seq is not NULL
        * @post this is not singular
        */
-      _Safe_local_iterator(const _Iterator& __i, const _Sequence* __seq)
-      : _Safe_local_iterator_base(__seq, _M_constant()), _M_current(__i)
+      _Safe_local_iterator(const _Iterator& __i,
+			   const _Safe_sequence_base* __cont)
+      : _Ite_base(__i), _Safe_base(__cont, _M_constant())
       {
 	_GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
 			      _M_message(__msg_init_singular)
@@ -97,9 +106,8 @@
       /**
        * @brief Copy construction.
        */
-      _Safe_local_iterator(const _Safe_local_iterator& __x)
-      : _Safe_local_iterator_base(__x, _M_constant()),
-	_M_current(__x._M_current)
+      _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
+      : _Ite_base(__x.base())
       {
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// DR 408. Is vector<reverse_iterator<char*> > forbidden?
@@ -108,9 +116,28 @@
 			      _M_message(__msg_init_copy_singular)
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
+	_M_attach(__x._M_sequence);
       }
 
       /**
+       * @brief Move construction.
+       * @post __x is singular and unattached
+       */
+      _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
+      : _Ite_base()
+      {
+	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
+			      || __x.base() == _Iterator(),
+			      _M_message(__msg_init_copy_singular)
+			      ._M_iterator(*this, "this")
+			      ._M_iterator(__x, "other"));
+	auto __cont = __x._M_sequence;
+	__x._M_detach();
+	std::swap(base(), __x.base());
+	_M_attach(__cont);
+      }
+
+      /**
        *  @brief Converting constructor from a mutable iterator to a
        *  constant iterator.
       */
@@ -121,8 +148,7 @@
 	      _MutableIterator,
 	      typename _Sequence::local_iterator::iterator_type>::__value,
 					  _Sequence>::__type>& __x)
-	: _Safe_local_iterator_base(__x, _M_constant()),
-	  _M_current(__x.base())
+	: _Ite_base(__x.base())
 	{
 	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
 	  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
@@ -131,6 +157,7 @@
 				_M_message(__msg_init_const_singular)
 				._M_iterator(*this, "this")
 				._M_iterator(__x, "other"));
+	  _M_attach(__x._M_sequence);
 	}
 
       /**
@@ -146,12 +173,58 @@
 			      _M_message(__msg_copy_singular)
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
-	_M_current = __x._M_current;
-	this->_M_attach(__x._M_sequence);
+
+	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
+	  {
+	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	    base() = __x.base();
+	    _M_version = __x._M_sequence->_M_version;
+	  }
+	else
+	  {
+	    _M_detach();
+	    base() = __x.base();
+	    _M_attach(__x._M_sequence);
+	  }
+
 	return *this;
       }
 
       /**
+       * @brief Move assignment.
+       * @post __x is singular and unattached
+       */
+      _Safe_local_iterator&
+      operator=(_Safe_local_iterator&& __x) noexcept
+      {
+	_GLIBCXX_DEBUG_VERIFY(this != &__x,
+			      _M_message(__msg_self_move_assign)
+			      ._M_iterator(*this, "this"));
+	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
+			      || __x.base() == _Iterator(),
+			      _M_message(__msg_copy_singular)
+			      ._M_iterator(*this, "this")
+			      ._M_iterator(__x, "other"));
+
+	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
+	  {
+	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	    base() = __x.base();
+	    _M_version = __x._M_sequence->_M_version;
+	  }
+	else
+	  {
+	    _M_detach();
+	    base() = __x.base();
+	    _M_attach(__x._M_sequence);
+	  }
+
+	__x._M_detach();
+	__x.base() = _Iterator();
+	return *this;
+      }
+
+      /**
        *  @brief Iterator dereference.
        *  @pre iterator is dereferenceable
        */
@@ -161,7 +234,7 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 			      _M_message(__msg_bad_deref)
 			      ._M_iterator(*this, "this"));
-	return *_M_current;
+	return *base();
       }
 
       /**
@@ -175,7 +248,7 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 			      _M_message(__msg_bad_deref)
 			      ._M_iterator(*this, "this"));
-	return std::__addressof(*_M_current);
+	return std::__addressof(*base());
       }
 
       // ------ Input iterator requirements ------
@@ -189,7 +262,8 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
-	++_M_current;
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	++base();
 	return *this;
       }
 
@@ -203,9 +277,9 @@
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
-	_Safe_local_iterator __tmp(*this);
-	++_M_current;
-	return __tmp;
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_local_iterator(base()++, this->_M_sequence,
+				    _Attach_single());
       }
 
       // ------ Utilities ------
@@ -212,30 +286,33 @@
       /**
        * @brief Return the underlying iterator
        */
-      _Iterator
-      base() const { return _M_current; }
+      _Iterator&
+      base() noexcept { return *this; }
 
+      const _Iterator&
+      base() const noexcept { return *this; }
+
       /**
        * @brief Return the bucket
        */
       size_type
-      bucket() const { return _M_current._M_get_bucket(); }
+      bucket() const { return base()._M_get_bucket(); }
 
       /**
        * @brief Conversion to underlying non-debug iterator to allow
        * better interaction with non-debug containers.
        */
-      operator _Iterator() const { return _M_current; }
+      operator _Iterator() const { return *this; }
 
       /** Attach iterator to the given sequence. */
       void
       _M_attach(_Safe_sequence_base* __seq)
-      { _Safe_iterator_base::_M_attach(__seq, _M_constant()); }
+      { _Safe_base::_M_attach(__seq, _M_constant()); }
 
       /** Likewise, but not thread-safe. */
       void
       _M_attach_single(_Safe_sequence_base* __seq)
-      { _Safe_iterator_base::_M_attach_single(__seq, _M_constant()); }
+      { _Safe_base::_M_attach_single(__seq, _M_constant()); }
 
       /// Is the iterator dereferenceable?
       bool
Index: include/debug/safe_sequence.tcc
===================================================================
--- include/debug/safe_sequence.tcc	(revision 215134)
+++ include/debug/safe_sequence.tcc	(working copy)
@@ -81,7 +81,8 @@
 
 	  for (_Safe_iterator_base* __iter = __from._M_iterators; __iter;)
 	    {
-	      iterator* __victim = static_cast<iterator*>(__iter);
+	      _Safe_iterator_base* __victim_base = __iter;
+	      iterator* __victim = static_cast<iterator*>(__victim_base);
 	      __iter = __iter->_M_next;
 	      if (!__victim->_M_singular() && __pred(__victim->base()))
 		{
@@ -88,14 +89,14 @@
 		  __victim->_M_detach_single();
 		  if (__transfered_iterators)
 		    {
-		      __victim->_M_next = __transfered_iterators;
-		      __transfered_iterators->_M_prior = __victim;
+		      __victim_base->_M_next = __transfered_iterators;
+		      __transfered_iterators->_M_prior = __victim_base;
 		    }
 		  else
-		    __last_iterator = __victim;
-		  __victim->_M_sequence = this;
-		  __victim->_M_version = this->_M_version;
-		  __transfered_iterators = __victim;
+		    __last_iterator = __victim_base;
+		  __victim_base->_M_sequence = this;
+		  __victim_base->_M_version = this->_M_version;
+		  __transfered_iterators = __victim_base;
 		}
 	    }
 
@@ -102,7 +103,9 @@
 	  for (_Safe_iterator_base* __iter2 = __from._M_const_iterators;
 		 __iter2;)
 	    {
-	      const_iterator* __victim = static_cast<const_iterator*>(__iter2);
+	      _Safe_iterator_base* __victim_base = __iter2;
+	      const_iterator* __victim =
+		static_cast<const_iterator*>(__victim_base);
 	      __iter2 = __iter2->_M_next;
 	      if (!__victim->_M_singular() && __pred(__victim->base()))
 		{
@@ -109,14 +112,14 @@
 		  __victim->_M_detach_single();
 		  if (__transfered_const_iterators)
 		    {
-		      __victim->_M_next = __transfered_const_iterators;
-		      __transfered_const_iterators->_M_prior = __victim;
+		      __victim_base->_M_next = __transfered_const_iterators;
+		      __transfered_const_iterators->_M_prior = __victim_base;
 		    }
 		  else
 		    __last_const_iterator = __victim;
-		  __victim->_M_sequence = this;
-		  __victim->_M_version = this->_M_version;
-		  __transfered_const_iterators = __victim;
+		  __victim_base->_M_sequence = this;
+		  __victim_base->_M_version = this->_M_version;
+		  __transfered_const_iterators = __victim_base;
 		}
 	    }
 	}
Index: include/debug/safe_unordered_base.h
===================================================================
--- include/debug/safe_unordered_base.h	(revision 215134)
+++ include/debug/safe_unordered_base.h	(working copy)
@@ -71,12 +71,6 @@
 			      bool __constant)
     { this->_M_attach(__x._M_sequence, __constant); }
 
-    _Safe_local_iterator_base&
-    operator=(const _Safe_local_iterator_base&);
-
-    explicit
-    _Safe_local_iterator_base(const _Safe_local_iterator_base&);
-
     ~_Safe_local_iterator_base() { this->_M_detach(); }
 
     _Safe_unordered_container_base*

Re: [Bug libstdc++/62313] Data race in debug iterators

[Jonathan Wakely]

On 10/09/14 22:55 +0200, François Dumont wrote:
>Hi
>
>    Here is a proposal to fix this data race issue.
>
>    I finally generalized bitset approach to fix it by inheriting from 
>the normal iterator first and then the _Safe_iterator_base type. None 
>of the libstdc++ iterator types are final so it is fine. Surprisingly, 
>despite inheritance being private gcc got confused between 
>_Safe_iterator_base _M_next and forward_list _M_next so I need to 
>adapt some code to make usage of _Safe_iterator_base _M_next explicit.

Access control in C++ is not related to visibility, name lookup still
finds private members, but it is an error to use them.

>    I also consider any operator where normal iterator is being 
>modified while the safe iterator is linked to the list of iterators. 
>This is necessary to make sure that thread sanatizer won't consider a 
>race condition. I didn't touch to bitset::reference because list 
>references are only access on bitset destruction which is clearly not 
>an operation allowed to do while playing with references in another 
>thread.
>
>    Do you see any way to check for this problem in the testsuite ? Is 
>there a thread sanitizer we could use ?

GCC's -fsanitize=thread option, although using it in the testsuite
would need something like dg-require-tsan so the test doesn't run on
platforms where it doesn't work, or if GCC was built without
libsanitizer.

Have you run some tests using -fsanitize=thread, even if they are not
in the testsuite?

>Index: include/debug/safe_iterator.h
>===================================================================
>--- include/debug/safe_iterator.h	(revision 215134)
>+++ include/debug/safe_iterator.h	(working copy)
>@@ -109,16 +109,21 @@
>    *  %_Safe_iterator has member functions for iterator invalidation,
>    *  attaching/detaching the iterator from sequences, and querying
>    *  the iterator's state.
>+   *
>+   *  Note that _Iterator must rely first in the type memory layout so that it

I can't parse this ... maybe "_Iterator must be the first base class" ?

>+   *  gets initialized before the iterator is being attached to the container

s/container/container's/

>+   *  list of iterators and it is being dettached before _Iterator get

s/dettached/detached/

>+   *  destroy. Otherwise it would result in a data race.

s/destroy/destroyed/

>    */
>   template<typename _Iterator, typename _Sequence>
>-    class _Safe_iterator : public _Safe_iterator_base
>+    class _Safe_iterator
>+    : private _Iterator,
>+      public _Safe_iterator_base
>     {
>-      typedef _Safe_iterator _Self;
>+      typedef _Iterator _Ite_base;

Please rename this to _Iter_base, "iter" is a more conventional
abbreviation than "ite"

>@@ -388,28 +433,27 @@
>       /**
>        * @brief Return the underlying iterator
>        */
>-      _Iterator
>-      base() const _GLIBCXX_NOEXCEPT { return _M_current; }
>+      _Iterator&
>+      base() _GLIBCXX_NOEXCEPT { return *this; }
> 
>+      const _Iterator&
>+      base() const _GLIBCXX_NOEXCEPT { return *this; }

I suppose base() doesn't need to be uglified to _M_base, because all
the containers already use std::reverse_iterator which uses the name
"base".

>Index: include/debug/safe_local_iterator.h
>===================================================================
>--- include/debug/safe_local_iterator.h	(revision 215134)
>+++ include/debug/safe_local_iterator.h	(working copy)
>@@ -49,15 +49,15 @@
>    *  the iterator's state.
>    */
>   template<typename _Iterator, typename _Sequence>
>-    class _Safe_local_iterator : public _Safe_local_iterator_base
>+    class _Safe_local_iterator
>+    : private _Iterator
>+    , public _Safe_local_iterator_base
>     {
>-      typedef _Safe_local_iterator _Self;
>+      typedef _Iterator _Ite_base;

Same renaming here please, to _Iter_base.

Apart from those minor adjustments I think this looks good, but I'd
like to know that it has been tested with -fsanitize=thread, even if
only lightly tested.

Re: [Bug libstdc++/62313] Data race in debug iterators

[François Dumont]

On 22/09/2014 00:04, Jonathan Wakely wrote:
> On 10/09/14 22:55 +0200, François Dumont wrote:
>> Hi
>>
>>    Here is a proposal to fix this data race issue.
>>
>>    I finally generalized bitset approach to fix it by inheriting from 
>> the normal iterator first and then the _Safe_iterator_base type. None 
>> of the libstdc++ iterator types are final so it is fine. 
>> Surprisingly, despite inheritance being private gcc got confused 
>> between _Safe_iterator_base _M_next and forward_list _M_next so I 
>> need to adapt some code to make usage of _Safe_iterator_base _M_next 
>> explicit.
>
> Access control in C++ is not related to visibility, name lookup still
> finds private members, but it is an error to use them.

Ok, tricky.

>
>>    I also consider any operator where normal iterator is being 
>> modified while the safe iterator is linked to the list of iterators. 
>> This is necessary to make sure that thread sanatizer won't consider a 
>> race condition. I didn't touch to bitset::reference because list 
>> references are only access on bitset destruction which is clearly not 
>> an operation allowed to do while playing with references in another 
>> thread.
>>
>>    Do you see any way to check for this problem in the testsuite ? Is 
>> there a thread sanitizer we could use ?
>
> GCC's -fsanitize=thread option, although using it in the testsuite
> would need something like dg-require-tsan so the test doesn't run on
> platforms where it doesn't work, or if GCC was built without
> libsanitizer.
>
> Have you run some tests using -fsanitize=thread, even if they are not
> in the testsuite?

No I hadn't and try since but without success. When I build with 
-fsanitize=thread the produced binary just segfault at startup. It 
complained about using -fPIE at compilation time and -lpie at link time 
but even with those options it segfault. Don't know what is going wrong. 
Maybe Dmitry who reported the bug could give it a try. I will ask for 
this on the bug ticket

>
>> Index: include/debug/safe_iterator.h
> Same renaming here please, to _Iter_base.
>
> Apart from those minor adjustments I think this looks good, but I'd
> like to know that it has been tested with -fsanitize=thread, even if
> only lightly tested.
>
>

I fixed the vocabulary problems. Just need a slight test then.

François

Re: [Bug libstdc++/62313] Data race in debug iterators

[Marek Polacek]

On Tue, Sep 23, 2014 at 10:42:31PM +0200, François Dumont wrote:
> No I hadn't and try since but without success. When I build with
> -fsanitize=thread the produced binary just segfault at startup. It
> complained about using -fPIE at compilation time and -lpie at link time but
> even with those options it segfault. Don't know what is going wrong. Maybe

At link time it should be -pie, not -lpie.

	Marek

Re: [Bug libstdc++/62313] Data race in debug iterators

[François Dumont]

>> Apart from those minor adjustments I think this looks good, but I'd
>> like to know that it has been tested with -fsanitize=thread, even if
>> only lightly tested.
>>
>>

Hi

     Dmitry, who reported the bug, confirmed the fix. Can I go ahead and 
commit ?

François

Re: [Bug libstdc++/62313] Data race in debug iterators

[Jonathan Wakely]

On 26/09/14 00:00 +0200, François Dumont wrote:
>
>>>Apart from those minor adjustments I think this looks good, but I'd
>>>like to know that it has been tested with -fsanitize=thread, even if
>>>only lightly tested.
>>>
>>>
>
>Hi
>
>    Dmitry, who reported the bug, confirmed the fix. Can I go ahead 
>and commit ?

Yes, OK.

Re: [Bug libstdc++/62313] Data race in debug iterators

[Jonathan Wakely]

On 26/09/14 11:05 +0100, Jonathan Wakely wrote:
>On 26/09/14 00:00 +0200, François Dumont wrote:
>>
>>>>Apart from those minor adjustments I think this looks good, but I'd
>>>>like to know that it has been tested with -fsanitize=thread, even if
>>>>only lightly tested.
>>>>
>>>>
>>
>>Hi
>>
>>   Dmitry, who reported the bug, confirmed the fix. Can I go ahead 
>>and commit ?
>
>Yes, OK.

This caused some failures in the printer tests:

Running
/home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/libstdc++-prettyprinters/prettyprinters.exp ...
FAIL: libstdc++-prettyprinters/debug.cc print deqiter
FAIL: libstdc++-prettyprinters/debug.cc print lstiter
FAIL: libstdc++-prettyprinters/debug.cc print lstciter
FAIL: libstdc++-prettyprinters/debug.cc print mpiter
FAIL: libstdc++-prettyprinters/debug.cc print spciter

Re: [Bug libstdc++/62313] Data race in debug iterators

[François Dumont]

I forgot to check pretty printer tests indeed, I will.

François

On 30/09/2014 17:32, Jonathan Wakely wrote:
> On 26/09/14 11:05 +0100, Jonathan Wakely wrote:
>> On 26/09/14 00:00 +0200, François Dumont wrote:
>>>
>>>>> Apart from those minor adjustments I think this looks good, but I'd
>>>>> like to know that it has been tested with -fsanitize=thread, even if
>>>>> only lightly tested.
>>>>>
>>>>>
>>>
>>> Hi
>>>
>>>   Dmitry, who reported the bug, confirmed the fix. Can I go ahead 
>>> and commit ?
>>
>> Yes, OK.
>
> This caused some failures in the printer tests:
>
> Running
> /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/libstdc++-prettyprinters/prettyprinters.exp 
> ...
> FAIL: libstdc++-prettyprinters/debug.cc print deqiter
> FAIL: libstdc++-prettyprinters/debug.cc print lstiter
> FAIL: libstdc++-prettyprinters/debug.cc print lstciter
> FAIL: libstdc++-prettyprinters/debug.cc print mpiter
> FAIL: libstdc++-prettyprinters/debug.cc print spciter
>
>

Re: [Bug libstdc++/62313] Data race in debug iterators

[François Dumont]

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

Hi

     I prefer to submit this patch to you cause I am not very 
comfortable with Python stuff.

     I simply rely on Python cast feature. It doesn't really matter but 
is it going to simply consider the debug iterator as a normal one or is 
it going through the C++ explicit cast operator on debug iterators ?

François


On 30/09/2014 17:32, Jonathan Wakely wrote:
> On 26/09/14 11:05 +0100, Jonathan Wakely wrote:
>> On 26/09/14 00:00 +0200, François Dumont wrote:
>>>
>>>>> Apart from those minor adjustments I think this looks good, but I'd
>>>>> like to know that it has been tested with -fsanitize=thread, even if
>>>>> only lightly tested.
>>>>>
>>>>>
>>>
>>> Hi
>>>
>>>   Dmitry, who reported the bug, confirmed the fix. Can I go ahead 
>>> and commit ?
>>
>> Yes, OK.
>
> This caused some failures in the printer tests:
>
> Running
> /home/jwakely/src/gcc/gcc/libstdc++-v3/testsuite/libstdc++-prettyprinters/prettyprinters.exp 
> ...
> FAIL: libstdc++-prettyprinters/debug.cc print deqiter
> FAIL: libstdc++-prettyprinters/debug.cc print lstiter
> FAIL: libstdc++-prettyprinters/debug.cc print lstciter
> FAIL: libstdc++-prettyprinters/debug.cc print mpiter
> FAIL: libstdc++-prettyprinters/debug.cc print spciter
>
>


[-- Attachment #2: pretty_printers.patch --]
[-- Type: text/x-patch, Size: 510 bytes --]

Index: python/libstdcxx/v6/printers.py
===================================================================
--- python/libstdcxx/v6/printers.py	(revision 215741)
+++ python/libstdcxx/v6/printers.py	(working copy)
@@ -460,7 +460,7 @@
     # and return the wrapped iterator value.
     def to_string (self):
         itype = self.val.type.template_argument(0)
-        return self.val['_M_current'].cast(itype)
+        return self.val.cast(itype)
 
 class StdMapPrinter:
     "Print a std::map or std::multimap"

Re: [Bug libstdc++/62313] Data race in debug iterators

[Jonathan Wakely]

On 30/09/14 22:18 +0200, François Dumont wrote:
>Hi
>
>    I prefer to submit this patch to you cause I am not very 
>comfortable with Python stuff.
>
>    I simply rely on Python cast feature. It doesn't really matter but 
>is it going to simply consider the debug iterator as a normal one or 

Yes.

>is it going through the C++ explicit cast operator on debug iterators 
>?

No, it doesn't call any C++ function.

(N.B. I was searching in debug/safe_iterator.h for the 'explicit'
conversion operator you referred to and was confused because I
couldn't find it, which is because the operator for converting to base
is not 'explicit')

I'm not sure why the existing Python code does .cast(itype) when
_M_current is already that type, that seems unnecessary to me, but
I think your fix is correct and OK to commit, thanks.