Re: [committed] libstdc++: Fix deadlock in debug iterator increment [PR108288]

["François Dumont" <frs.dumont@gmail.com>]

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

Thanks for fixing this.

Here is the extension of the fix to all post-increment/decrement 
operators we have on _GLIBCXX_DEBUG iterator.

I prefer to restore somehow previous implementation to continue to have 
_GLIBCXX_DEBUG post operators implemented in terms of normal post operators.

I also plan to remove the debug check in the _Safe_iterator constructor 
from base iterator to avoid the redundant check we have now. But I need 
to make sure first that we are never calling it with an unchecked base 
iterator. And it might not be the right moment to do such a change.

     libstdc++: Fix deadlock in debug local_iterator increment [PR108288]

     Complete fix on all _Safe_iterator post-increment and 
post-decrement implementations
     and on _Safe_local_iterator.

     libstdc++-v3/ChangeLog:

             * include/debug/safe_iterator.h 
(_Safe_iterator<>::operator++(int)): Extend deadlock fix to
             other iterator category.
             (_Safe_iterator<>::operator--(int)): Likewise.
             * include/debug/safe_local_iterator.h 
(_Safe_local_iterator<>::operator++(int)): Fix deadlock.
             * testsuite/util/debug/unordered_checks.h 
(invalid_local_iterator_pre_increment): New.
             (invalid_local_iterator_post_increment): New.
             * 
testsuite/23_containers/unordered_map/debug/invalid_local_iterator_post_increment_neg.cc:
             New test.
             * 
testsuite/23_containers/unordered_map/debug/invalid_local_iterator_pre_increment_neg.cc:
             New test.

Tested under Linux x86_64.

Ok to commit ?

François

On 06/01/23 12:54, Jonathan Wakely via Libstdc++ wrote:
> Tested x86_64-linux. Pushed to trunk.
>
> I think we should backport this too, after some soak time on trunk.
>
> -- >8 --
>
> With -fno-elide-constructors the debug iterator post-increment and
> post-decrement operators are susceptible to deadlock. They take a mutex
> lock and then return a temporary, which also attempts to take a lock to
> attach itself to the sequence. If the return value and *this happen to
Note that the chosen mutex depends on the sequence so there is no need 
for conditional sentense here, it will necessarily be the same mutex.
> collide and use the same mutex from the pool, then you get a deadlock
> trying to lock a mutex that is already held by the current thread.

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

diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index f9068eaf8d6..e7c96d1af27 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -129,14 +129,6 @@ namespace __gnu_debug
 	typename _Sequence::_Base::iterator,
 	typename _Sequence::_Base::const_iterator>::__type _OtherIterator;
 
-      struct _Attach_single
-      { };
-
-      _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
-      _GLIBCXX_NOEXCEPT
-      : _Iter_base(__i)
-      { _M_attach_single(__seq); }
-
     public:
       typedef _Iterator					iterator_type;
       typedef typename _Traits::iterator_category	iterator_category;
@@ -347,8 +339,13 @@ namespace __gnu_debug
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
-	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
+	_Iter_base __cur;
+	{
+	  __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	  __cur = base()++;
+	}
+
+	return _Safe_iterator(__cur, this->_M_sequence);
       }
 
       // ------ Utilities ------
@@ -520,12 +517,6 @@ namespace __gnu_debug
 
     protected:
       typedef typename _Safe_base::_OtherIterator _OtherIterator;
-      typedef typename _Safe_base::_Attach_single _Attach_single;
-
-      _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
-      _GLIBCXX_NOEXCEPT
-      : _Safe_base(__i, __seq, _Attach_single())
-      { }
 
     public:
       /// @post the iterator is singular and unattached
@@ -609,9 +600,13 @@ namespace __gnu_debug
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
-	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	return _Safe_iterator(this->base()++, this->_M_sequence,
-			      _Attach_single());
+	_Iter_base __cur;
+	{
+	  __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	  __cur = this->base()++;
+	}
+
+	return _Safe_iterator(__cur, this->_M_sequence);
       }
 
       // ------ Bidirectional iterator requirements ------
@@ -640,9 +635,13 @@ namespace __gnu_debug
 	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 			      _M_message(__msg_bad_dec)
 			      ._M_iterator(*this, "this"));
-	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	return _Safe_iterator(this->base()--, this->_M_sequence,
-			      _Attach_single());
+	_Iter_base __cur;
+	{
+	  __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	  __cur = this->base()--;
+	}
+
+	return _Safe_iterator(__cur, this->_M_sequence);
       }
 
       // ------ Utilities ------
@@ -666,13 +665,6 @@ namespace __gnu_debug
       typedef _Safe_iterator<_OtherIterator, _Sequence,
 			     std::random_access_iterator_tag> _OtherSelf;
 
-      typedef typename _Safe_base::_Attach_single _Attach_single;
-
-      _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
-      _GLIBCXX_NOEXCEPT
-      : _Safe_base(__i, __seq, _Attach_single())
-      { }
-
     public:
       typedef typename _Safe_base::difference_type	difference_type;
       typedef typename _Safe_base::reference		reference;
@@ -761,9 +753,16 @@ namespace __gnu_debug
       _Safe_iterator
       operator++(int) _GLIBCXX_NOEXCEPT
       {
-	_Safe_iterator __ret = *this;
-	++*this;
-	return __ret;
+	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
+			      _M_message(__msg_bad_inc)
+			      ._M_iterator(*this, "this"));
+	_Iter_base __cur;
+	{
+	  __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	  __cur = this->base()++;
+	}
+
+	return _Safe_iterator(__cur, this->_M_sequence);
       }
 
       // ------ Bidirectional iterator requirements ------
@@ -785,9 +784,16 @@ namespace __gnu_debug
       _Safe_iterator
       operator--(int) _GLIBCXX_NOEXCEPT
       {
-	_Safe_iterator __ret = *this;
-	--*this;
-	return __ret;
+	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
+			      _M_message(__msg_bad_dec)
+			      ._M_iterator(*this, "this"));
+	_Iter_base __cur;
+	{
+	  __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	  __cur = this->base()--;
+	}
+
+	return _Safe_iterator(__cur, this->_M_sequence);
       }
 
       // ------ Random access iterator requirements ------
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h
index 6e3c4eb1505..3c525652ea1 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.h
+++ b/libstdc++-v3/include/debug/safe_local_iterator.h
@@ -84,14 +84,6 @@ namespace __gnu_debug
       typedef _Safe_local_iterator _Self;
       typedef _Safe_local_iterator<_OtherIterator, _Sequence> _OtherSelf;
 
-      struct _Attach_single
-      { };
-
-      _Safe_local_iterator(_Iterator __i, _Safe_sequence_base* __cont,
-			   _Attach_single) noexcept
-      : _Iter_base(__i)
-      { _M_attach_single(__cont); }
-
     public:
       typedef _Iterator					iterator_type;
       typedef typename _Traits::iterator_category	iterator_category;
@@ -290,9 +282,13 @@ namespace __gnu_debug
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
-	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	return _Safe_local_iterator(base()++, this->_M_sequence,
-				    _Attach_single());
+	_Iter_base __cur;
+	{
+	  __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	  __cur = base()++;
+	}
+
+	return { __cur, this->_M_sequence };
       }
 
       // ------ Utilities ------
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/invalid_local_iterator_post_increment_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/invalid_local_iterator_post_increment_neg.cc
new file mode 100644
index 00000000000..74005c3ec69
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/invalid_local_iterator_post_increment_neg.cc
@@ -0,0 +1,16 @@
+// { dg-do run { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <debug/unordered_checks.h>
+
+void test01()
+{
+  __gnu_test::invalid_local_iterator_post_increment<std::unordered_map<int, int>>();
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/invalid_local_iterator_pre_increment_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/invalid_local_iterator_pre_increment_neg.cc
new file mode 100644
index 00000000000..016cd1c6947
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/invalid_local_iterator_pre_increment_neg.cc
@@ -0,0 +1,16 @@
+// { dg-do run { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <debug/unordered_checks.h>
+
+void test01()
+{
+  __gnu_test::invalid_local_iterator_pre_increment<std::unordered_map<int, int>>();
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/util/debug/unordered_checks.h b/libstdc++-v3/testsuite/util/debug/unordered_checks.h
index 655f16f199f..971fe68396b 100644
--- a/libstdc++-v3/testsuite/util/debug/unordered_checks.h
+++ b/libstdc++-v3/testsuite/util/debug/unordered_checks.h
@@ -125,6 +125,38 @@ namespace __gnu_test
       VERIFY( *it == val );
     }
 
+  template<typename _Tp>
+    void invalid_local_iterator_pre_increment()
+    {
+      typedef _Tp cont_type;
+      typedef typename cont_type::value_type cont_val_type;
+      typedef typename CopyableValueType<cont_val_type>::value_type val_type;
+      generate_unique<val_type> gu;
+
+      cont_type c;
+      for (size_t i = 0; i != 5; ++i)
+	c.insert(gu.build());
+
+      for (auto lit = c.begin(0); ;)
+	++lit;
+    }
+
+  template<typename _Tp>
+    void invalid_local_iterator_post_increment()
+    {
+      typedef _Tp cont_type;
+      typedef typename cont_type::value_type cont_val_type;
+      typedef typename CopyableValueType<cont_val_type>::value_type val_type;
+      generate_unique<val_type> gu;
+
+      cont_type c;
+      for (size_t i = 0; i != 5; ++i)
+	c.insert(gu.build());
+
+      for (auto it = c.begin(0); ;)
+	it++;
+    }
+
   template<typename _Tp>
     void invalid_local_iterator_compare()
     {