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

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

[Jonathan Wakely]

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
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.

The solution is to construct the return value before taking the lock.
The copy constructor and pre-inc/pre-dec operators already manage locks
correctly, without deadlock, so just implement post-inc/post-dec in the
conventional way, taking a copy then modifying *this, then returning the
copy.

libstdc++-v3/ChangeLog:

	PR libstdc++/108288
	* include/debug/safe_iterator.h (_Safe_iterator::operator++(int))
	(_Safe_iterator::operator--(int)): Do not hold lock around
	construction of return value.
---
 libstdc++-v3/include/debug/safe_iterator.h | 18 ++++++------------
 1 file changed, 6 insertions(+), 12 deletions(-)

diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index 117dc93de60..f9068eaf8d6 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -761,12 +761,9 @@ namespace __gnu_debug
       _Safe_iterator
       operator++(int) _GLIBCXX_NOEXCEPT
       {
-	_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());
+	_Safe_iterator __ret = *this;
+	++*this;
+	return __ret;
       }
 
       // ------ Bidirectional iterator requirements ------
@@ -788,12 +785,9 @@ namespace __gnu_debug
       _Safe_iterator
       operator--(int) _GLIBCXX_NOEXCEPT
       {
-	_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());
+	_Safe_iterator __ret = *this;
+	--*this;
+	return __ret;
       }
 
       // ------ Random access iterator requirements ------
-- 
2.39.0

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

[François Dumont]

[-- 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()
     {

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

[François Dumont]

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

Small update for an obvious compilation issue and to review new test 
case that could have lead to an infinite loop if the increment issue was 
not detected.

I also forgot to ask if there is more chance for the instantiation to be 
elided when it is implemented like in the _Safe_local_iterator:
return { __cur, this->_M_sequence };

than in the _Safe_iterator:
return _Safe_iterator(__cur, this->_M_sequence);

In the case where the user code do not use it ?

Fully tested now, ok to commit ?

François

On 11/01/23 07:03, François Dumont wrote:
> 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: 8372 bytes --]

diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index f9068eaf8d6..f8b46826b7c 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());
+	_Iterator __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());
+	_Iterator __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"));
+	_Iterator __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"));
+	_Iterator __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..76ae05bbf8b 100644
--- a/libstdc++-v3/testsuite/util/debug/unordered_checks.h
+++ b/libstdc++-v3/testsuite/util/debug/unordered_checks.h
@@ -125,6 +125,40 @@ 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());
+
+      auto lit = c.begin(0);
+      for (size_t i = 0; i != 6; ++i)
+	++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());
+
+      auto lit = c.begin(0);
+      for (size_t i = 0; i != 6; ++i)
+	lit++;
+    }
+
   template<typename _Tp>
     void invalid_local_iterator_compare()
     {

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

[Jonathan Wakely]

On Thu, 12 Jan 2023 at 05:52, François Dumont wrote:
>
> Small update for an obvious compilation issue and to review new test
> case that could have lead to an infinite loop if the increment issue was
> not detected.
>
> I also forgot to ask if there is more chance for the instantiation to be
> elided when it is implemented like in the _Safe_local_iterator:
> return { __cur, this->_M_sequence };

No, that doesn't make any difference.

>
> than in the _Safe_iterator:
> return _Safe_iterator(__cur, this->_M_sequence);
>
> In the case where the user code do not use it ?
>
> Fully tested now, ok to commit ?
>
> François
>
> On 11/01/23 07:03, François Dumont wrote:
> > Thanks for fixing this.
> >
> > Here is the extension of the fix to all post-increment/decrement
> > operators we have on _GLIBCXX_DEBUG iterator.

Thanks, I completely forgot we have other partial specializations, I
just fixed the one that showed a deadlock in the user's example!

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

Why?

Implementing post-increment as:

    auto tmp = *this;
    ++*this;
    return tmp;

is the idiomatic way to write it, and it works fine in this case. I
don't think it performs any more work than your version, does it?
Why not use the idiomatic form?

Is it just so that post-inc of a debug iterator uses post-inc of the
underlying iterator? Why does that matter?

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

[François Dumont]

On 12/01/23 13:00, Jonathan Wakely wrote:
> On Thu, 12 Jan 2023 at 05:52, François Dumont wrote:
>> Small update for an obvious compilation issue and to review new test
>> case that could have lead to an infinite loop if the increment issue was
>> not detected.
>>
>> I also forgot to ask if there is more chance for the instantiation to be
>> elided when it is implemented like in the _Safe_local_iterator:
>> return { __cur, this->_M_sequence };
> No, that doesn't make any difference.
>
>> than in the _Safe_iterator:
>> return _Safe_iterator(__cur, this->_M_sequence);
>>
>> In the case where the user code do not use it ?
>>
>> Fully tested now, ok to commit ?
>>
>> François
>>
>> On 11/01/23 07:03, François Dumont wrote:
>>> Thanks for fixing this.
>>>
>>> Here is the extension of the fix to all post-increment/decrement
>>> operators we have on _GLIBCXX_DEBUG iterator.
> Thanks, I completely forgot we have other partial specializations, I
> just fixed the one that showed a deadlock in the user's example!
>
>>> I prefer to restore somehow previous implementation to continue to
>>> have _GLIBCXX_DEBUG post operators implemented in terms of normal post
>>> operators.
> Why?
>
> Implementing post-increment as:
>
>      auto tmp = *this;
>      ++*this;
>      return tmp;
>
> is the idiomatic way to write it, and it works fine in this case. I
> don't think it performs any more work than your version, does it?
> Why not use the idiomatic form?
>
> Is it just so that post-inc of a debug iterator uses post-inc of the
> underlying iterator? Why does that matter?
>
A little yes, but that's a minor reason that is just making me happy.

Main reason is that this form could produce a __msg_init_copy_singular 
before the __msg_bad_inc.

And moreover I plan to propose a patch later to skip any check in the 
call to _Safe_iterator(__cur, _M_sequence) as we already know that __cur 
is ok here like anywhere else in the lib.

There will still be one in the constructor normally elided unless 
--no-elide-constructors but there is not much I can do about it.

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

[Jonathan Wakely]

On Thu, 12 Jan 2023 at 18:25, François Dumont <frs.dumont@gmail.com> wrote:
>
> On 12/01/23 13:00, Jonathan Wakely wrote:
> > On Thu, 12 Jan 2023 at 05:52, François Dumont wrote:
> >> Small update for an obvious compilation issue and to review new test
> >> case that could have lead to an infinite loop if the increment issue was
> >> not detected.
> >>
> >> I also forgot to ask if there is more chance for the instantiation to be
> >> elided when it is implemented like in the _Safe_local_iterator:
> >> return { __cur, this->_M_sequence };
> > No, that doesn't make any difference.
> >
> >> than in the _Safe_iterator:
> >> return _Safe_iterator(__cur, this->_M_sequence);
> >>
> >> In the case where the user code do not use it ?
> >>
> >> Fully tested now, ok to commit ?
> >>
> >> François
> >>
> >> On 11/01/23 07:03, François Dumont wrote:
> >>> Thanks for fixing this.
> >>>
> >>> Here is the extension of the fix to all post-increment/decrement
> >>> operators we have on _GLIBCXX_DEBUG iterator.
> > Thanks, I completely forgot we have other partial specializations, I
> > just fixed the one that showed a deadlock in the user's example!
> >
> >>> I prefer to restore somehow previous implementation to continue to
> >>> have _GLIBCXX_DEBUG post operators implemented in terms of normal post
> >>> operators.
> > Why?
> >
> > Implementing post-increment as:
> >
> >      auto tmp = *this;
> >      ++*this;
> >      return tmp;
> >
> > is the idiomatic way to write it, and it works fine in this case. I
> > don't think it performs any more work than your version, does it?
> > Why not use the idiomatic form?
> >
> > Is it just so that post-inc of a debug iterator uses post-inc of the
> > underlying iterator? Why does that matter?
> >
> A little yes, but that's a minor reason that is just making me happy.
>
> Main reason is that this form could produce a __msg_init_copy_singular
> before the __msg_bad_inc.

Ah yes, I see. That's a shame. I find the idiomatic form much simpler
to read, and it will generate better code (because it just reuses
existing functions, instead of adding new ones).

We could do this though, right?

    _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
                  _M_message(__msg_bad_inc)
                  ._M_iterator(*this, "this"));
    _Safe_iterator __tmp = *this;
    ++*this;
    return __tmp;

That does the VERIFY check twice though.

> And moreover I plan to propose a patch later to skip any check in the
> call to _Safe_iterator(__cur, _M_sequence) as we already know that __cur
> is ok here like anywhere else in the lib.
>
> There will still be one in the constructor normally elided unless
> --no-elide-constructors but there is not much I can do about it.

Don't worry about it. Nobody should ever use -fno-elide-constructors
in any real cases (except maybe debugging some very strange corner
cases, and in that case the extra safe iterator checks are not going
to be their biggest problem).

The patch is OK for trunk then.

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

[François Dumont]

Committed with the idiomatic approach.

I'll work on this additional check later.

On 12/01/23 22:35, Jonathan Wakely wrote:
> On Thu, 12 Jan 2023 at 18:25, François Dumont <frs.dumont@gmail.com> wrote:
>> On 12/01/23 13:00, Jonathan Wakely wrote:
>>> On Thu, 12 Jan 2023 at 05:52, François Dumont wrote:
>>>> Small update for an obvious compilation issue and to review new test
>>>> case that could have lead to an infinite loop if the increment issue was
>>>> not detected.
>>>>
>>>> I also forgot to ask if there is more chance for the instantiation to be
>>>> elided when it is implemented like in the _Safe_local_iterator:
>>>> return { __cur, this->_M_sequence };
>>> No, that doesn't make any difference.
>>>
>>>> than in the _Safe_iterator:
>>>> return _Safe_iterator(__cur, this->_M_sequence);
>>>>
>>>> In the case where the user code do not use it ?
>>>>
>>>> Fully tested now, ok to commit ?
>>>>
>>>> François
>>>>
>>>> On 11/01/23 07:03, François Dumont wrote:
>>>>> Thanks for fixing this.
>>>>>
>>>>> Here is the extension of the fix to all post-increment/decrement
>>>>> operators we have on _GLIBCXX_DEBUG iterator.
>>> Thanks, I completely forgot we have other partial specializations, I
>>> just fixed the one that showed a deadlock in the user's example!
>>>
>>>>> I prefer to restore somehow previous implementation to continue to
>>>>> have _GLIBCXX_DEBUG post operators implemented in terms of normal post
>>>>> operators.
>>> Why?
>>>
>>> Implementing post-increment as:
>>>
>>>       auto tmp = *this;
>>>       ++*this;
>>>       return tmp;
>>>
>>> is the idiomatic way to write it, and it works fine in this case. I
>>> don't think it performs any more work than your version, does it?
>>> Why not use the idiomatic form?
>>>
>>> Is it just so that post-inc of a debug iterator uses post-inc of the
>>> underlying iterator? Why does that matter?
>>>
>> A little yes, but that's a minor reason that is just making me happy.
>>
>> Main reason is that this form could produce a __msg_init_copy_singular
>> before the __msg_bad_inc.
> Ah yes, I see. That's a shame. I find the idiomatic form much simpler
> to read, and it will generate better code (because it just reuses
> existing functions, instead of adding new ones).
>
> We could do this though, right?
>
>      _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
>                    _M_message(__msg_bad_inc)
>                    ._M_iterator(*this, "this"));
>      _Safe_iterator __tmp = *this;
>      ++*this;
>      return __tmp;
>
> That does the VERIFY check twice though.
>
>> And moreover I plan to propose a patch later to skip any check in the
>> call to _Safe_iterator(__cur, _M_sequence) as we already know that __cur
>> is ok here like anywhere else in the lib.
>>
>> There will still be one in the constructor normally elided unless
>> --no-elide-constructors but there is not much I can do about it.
> Don't worry about it. Nobody should ever use -fno-elide-constructors
> in any real cases (except maybe debugging some very strange corner
> cases, and in that case the extra safe iterator checks are not going
> to be their biggest problem).
>
> The patch is OK for trunk then.
>