Re: Improve safe iterator move semantic

[Jonathan Wakely <jwakely at redhat dot com>]

On 09/08/18 20:41 +0200, François Dumont wrote:
>     Here is a patch to improve Debug mode safe iterator move semantic.
>
>     To summarize where we used to have N mutex locks we now have N - 
> 1. For instance move constructor used to lock mutex twice, now it only 
> does it once. Note that move constructor or move assignment operator 
> are currently more expensive than their copy counterparts !

Yes, because they have to mutate two objects, not just one. We could
just remove the move operations, and so all "moves" just do copies
instead. That would not allow Dbueg Mode to assert on operations on
moved-from iterators. Do we care about that?

Do any of our (non-debug) container iterators actually become invalid
after a move, or are they all safe to keep using?


> +#if __cplusplus >= 201103L
> +    _Safe_iterator_base(_Safe_iterator_base&&) = default;
> +
> +    _Safe_iterator_base&
> +    operator=(_Safe_iterator_base&&) = default;
> +#endif

This is very counterintuitive. The type has pointer members, so moving
doesn't set them to null, it's just a copy. In the derived moves we do
an explicit _M_reset() later, to make it more "move-like", but the
base operation is still a copy.

We would need **at least** a comment on the defaulted move operations
saying "these just copy the members, but then the derived class clears
them after adjusting pointers for the sequence's other iterators".

But there's another counterintuitive problem: in C++98 mode _Safe_base
has an implicit (public) copy constructor and copy assignment
operator, but in C++11 mode those are suppressed by the (protected)
move constructor and move assignment operator. Either we should
declare private+undefined copy ops in C++98 mode (to make them
consistently unavailable), or just change the defaulted move into
defaulted copies (since that's what they do anyway).

Or alternatively, don't define a move constructor and move assignment
operator at all, and delete copies and moves. The derived
_Safe_iterator move ctor and move assignment can both use the same
function _M_move to do the moving and the resetting all at once. See
the attached patch (relative to yours) to see what I mean.

BUT, I think the whole concept of reducing the number of mutex locks
is flawed. See below.


> @@ -148,11 +161,12 @@ namespace __gnu_debug
>
>     /** Reset all member variables */
>     void
> -    _M_reset() throw ();
> +    _M_reset() _GLIBCXX_USE_NOEXCEPT
> +    { __builtin_memset(this, 0, sizeof(_Safe_iterator_base)); }

This is undefined behaviour, because _Safe_iterator_base is not
trivially copyable. Adding a static assertion shows:

In file included from /home/jwakely/src/gcc/gcc/libstdc++-v3/src/c++11/debug.cc:29:
/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/debug/safe_base.h:179:17: error: static assertion failed
  static_assert(std::is_trivially_copyable<_Safe_iterator_base>::value, "");
                ^~~


> +  inline void
> +  _Safe_local_iterator_base::_M_move_to(_Safe_iterator_base* __x,
> +					bool __constant)
> +  {
> +    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
> +    if (_M_prior)
> +      _M_prior->_M_next = this;
> +    else
> +      {
> +	// No prior, we are at the beginning of the linked list.
> +	auto& __its = __constant
> +	  ? _M_get_container()->_M_const_local_iterators
> +	  : _M_get_container()->_M_local_iterators;
> +	if (__its == __x)
> +	  __its = this;
> +      }
> +
> +    if (_M_next)
> +      _M_next->_M_prior = this;
> +  }

This is not thread-safe. What if another thread is modifying
*__x._M_prior at the same time? It will lock
__x._M_prior->_M_get_mutex(), and then try to update
*__x._M_prior->_M_next, which is __x.

But nothing locks __x._M_get_mutex() to make that safe.

This valid program shows data races with -fsanitize=thread after your
patch is applied:

#define _GLIBCXX_DEBUG
#include <vector>
#include <thread>

void thrash(std::vector<int>::iterator& iter)
{
 for (int i = 0; i < 1000; ++i)
 {
   auto jiter = std::move(iter);
   iter = std::move(jiter);
   jiter = std::move(iter);
   iter = std::move(jiter);
 }
}

int main()
{
 std::vector<int> v{1, 2, 3};
 auto it1 = v.begin();
 auto it2 = v.begin();
 std::thread t1(thrash, std::ref(it1));
 thrash(it2);
 t1.join();
}

(It also shows data races with my version of the patch attached to
this mail, because my patch only refactors yours a bit, it doesn't
change how the mutexes are locked).

I think this idea is fundamentally flawed.


diff --git a/libstdc++-v3/include/debug/safe_base.h b/libstdc++-v3/include/debug/safe_base.h
index c276a1883a1..aa6fc76ec42 100644
--- a/libstdc++-v3/include/debug/safe_base.h
+++ b/libstdc++-v3/include/debug/safe_base.h
@@ -97,13 +97,6 @@ namespace __gnu_debug
     : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
     { this->_M_attach(__x._M_sequence, __constant); }
 
-#if __cplusplus >= 201103L
-    _Safe_iterator_base(_Safe_iterator_base&&) = default;
-
-    _Safe_iterator_base&
-    operator=(_Safe_iterator_base&&) = default;
-#endif
-
     ~_Safe_iterator_base() { this->_M_detach(); }
 
     /** For use in _Safe_iterator. */
@@ -129,9 +122,8 @@ namespace __gnu_debug
     _M_detach();
 
 #if __cplusplus >= 201103L
-    /** Attaches this iterator at __x place. */
     void
-    _M_move_to(_Safe_iterator_base* __x, bool __constant);
+    _M_move_base(_Safe_iterator_base&& __x, bool __constant);
 #endif
 
   public:
@@ -159,11 +151,6 @@ namespace __gnu_debug
     _M_invalidate()
     { _M_version = 0; }
 
-    /** Reset all member variables */
-    void
-    _M_reset() _GLIBCXX_USE_NOEXCEPT
-    { __builtin_memset(this, 0, sizeof(_Safe_iterator_base)); }
-
     /** Unlink itself */
     void
     _M_unlink() _GLIBCXX_USE_NOEXCEPT
@@ -173,6 +160,16 @@ namespace __gnu_debug
       if (_M_next)
 	_M_next->_M_prior = _M_prior;
     }
+
+#if __cplusplus >= 201103L
+    // Copying should be done manually by the derived class.
+    _Safe_iterator_base(const _Safe_iterator_base&) = delete;
+    _Safe_iterator_base& operator=(const _Safe_iterator_base&) = delete;
+#else
+  private:
+    _Safe_iterator_base(const _Safe_iterator_base&); // undefined
+    _Safe_iterator_base& operator=(const _Safe_iterator_base&); // undefined
+#endif
   };
 
   /** Iterators that derive from _Safe_iterator_base can be determined singular
@@ -290,22 +287,33 @@ namespace __gnu_debug
 
 #if __cplusplus >= 201103L
   inline void
-  _Safe_iterator_base::_M_move_to(_Safe_iterator_base* __x, bool __constant)
+  _Safe_iterator_base::_M_move_base(_Safe_iterator_base&& __x, bool __constant)
   {
-    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-    if (_M_prior)
-      _M_prior->_M_next = this;
-    else
-      {
-	// No prior, we are at the beginning of the linked list.
-	auto& __its = __constant
-	  ? _M_sequence->_M_const_iterators : _M_sequence->_M_iterators;
-	if (__its == __x)
-	  __its = this;
-      }
-
-    if (_M_next)
-      _M_next->_M_prior = this;
+    _M_sequence = __x._M_sequence;
+    _M_version = __x._M_version;
+    _M_next = __x._M_next;
+    _M_prior = __x._M_prior;
+    {
+      __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+      if (__x._M_prior)
+	__x._M_prior->_M_next = this;
+      else
+	{
+	  // No prior, we are at the beginning of the linked list.
+	  auto& __its = __constant
+	    ? _M_sequence->_M_const_iterators : _M_sequence->_M_iterators;
+	  if (__its == &__x)
+	    __its = this;
+	}
+
+      if (__x._M_next)
+	__x._M_next->_M_prior = this;
+    }
+
+    __x._M_sequence = nullptr;
+    __x._M_version = 0;
+    __x._M_next = nullptr;
+    __x._M_prior = nullptr;
   }
 #endif
 
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index 4b5773f16e2..39fa2e890c8 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -151,7 +151,7 @@ namespace __gnu_debug
        * @post __x is singular and unattached
        */
       _Safe_iterator(_Safe_iterator&& __x) noexcept
-      : _Iter_base(__x), _Safe_base(std::move(__x))
+      : _Iter_base(__x), _Safe_base()
       {
 	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 			      || __x.base() == _Iterator(),
@@ -160,9 +160,7 @@ namespace __gnu_debug
 			      ._M_iterator(__x, "other"));
 	if (__x._M_sequence)
 	  {
-	    _M_move_to(&__x, _S_constant());
-
-	    __x._M_reset();
+	    _M_move_base(std::move(__x), _S_constant());
 	    __x.base() = _Iter_base();
 	  }
       }
@@ -243,6 +241,7 @@ namespace __gnu_debug
 	    base() = __x.base();
 	    _M_version = __x._M_version;
 	    __x._M_detach_single();
+	    __x.base() = _Iterator();
 	  }
 	else
 	  {
@@ -251,13 +250,10 @@ namespace __gnu_debug
 
 	    if (__x._M_sequence)
 	      {
-		_Safe_base::operator=(std::move(__x));
-		_M_move_to(&__x, _S_constant());
-		__x._M_reset();
+		_M_move_base(std::move(__x), _S_constant());
+		__x.base() = _Iterator();
 	      }
 	  }
-
-	__x.base() = _Iterator();
 	return *this;
       }
 #endif