Improve safe iterator move semantic

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 !

     I did my best to avoid new symbols but I still require 1 to be 
added: _Safe_local_iterator::_M_attach_single. We will now make use of 
the already exported _Safe_iterator::_M_attach_single symbol.

     Tested under Linux x86_64, Debug mode.

Ok to commit ?

François

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

On 10/08/18 11:00 +0100, Jonathan Wakely wrote:
>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();
>}

Doing a test like this with TSan should be the absolute minimum
required for any change to the mutex locking policy.

You want to reduce the locks on move operations of iterators? OK,
perform lots of move operations on two iterators from the same
sequence and see if ThreadSanitizer shows errors.

If TSan doesn't show errors, adjust the test and try harder to prove
it's correct. Maybe your test was flawed. For example, my first
attempt to prove the data race passed the iterators by value not by
reference. That meant there were more than two debug iterators in the
linked list, and so the two iterators being tested were not adjacent
in the list, and didn't conflict. Because I'd already proved there was
a bug by inspecting the code I knew my test was flawed, so I changed
it. But even if I hadn't already proved a bug, I would have kept
testing different variations to prove whether the code was correct or
not.

Our debug iterators make "non-local" modifications to other objects
from the same sequence. That needs careful synchronisation. If that
makes the code a bit slower, then we just have to live with it.
Correct and slow is better than fast and wrong.

I'm not aware of people complaining about the performance of debug
mode anyway. Everybody I speak to is happy to accept a performance hit
in order to get checking.

I think https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86843 would be
more helpful to our users, as it would allow some Debug Mode checks to
be enabled in programs that can't currently use it (because
recompiling the entire program is not possible).

On 10 August 2018 at 13:47, Jonathan Wakely <jwakely@redhat.com> wrote:
> Doing a test like this with TSan should be the absolute minimum
> required for any change to the mutex locking policy.

Agreed. Concurrency code is something that our test suite is not
well-equipped to test (because
it doesn't support TSan and such yet), so it would seem prudent to
stress-test such patches
via testsuite-external means.

> I'm not aware of people complaining about the performance of debug
> mode anyway. Everybody I speak to is happy to accept a performance hit
> in order to get checking.

Yep; while it's nice to have performance improvements in debug mode,
there are probably more
important and significant ways to improve it..

> I think https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86843 would be
> more helpful to our users, as it would allow some Debug Mode checks to
> be enabled in programs that can't currently use it (because
> recompiling the entire program is not possible).

..like this one, which would be a major usability improvement.

On 10/08/2018 13:26, Ville Voutilainen wrote:
> On 10 August 2018 at 13:47, Jonathan Wakely <jwakely@redhat.com> wrote:
>> Doing a test like this with TSan should be the absolute minimum
>> required for any change to the mutex locking policy.
> Agreed. Concurrency code is something that our test suite is not
> well-equipped to test (because
> it doesn't support TSan and such yet), so it would seem prudent to
> stress-test such patches
> via testsuite-external means.

Yes, sorry about that, I am over confident in the testsuite indeed.

And I also totally forgot this use case of 2 threads playing with 
iterators on the same container. So I didn't even try to find out if any 
test could be good to simulate it.

Now, considering this episode, I am incline to just delete safe iterator 
move semantic. I might propose a patch to do so later.

>
>> I'm not aware of people complaining about the performance of debug
>> mode anyway. Everybody I speak to is happy to accept a performance hit
>> in order to get checking.
Good to know, I just hope you will accept one more patch regarding 
another performance hint of debug mode when using deque::iterator.
> Yep; while it's nice to have performance improvements in debug mode,
> there are probably more
> important and significant ways to improve it..
>
>> I think https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86843 would be
>> more helpful to our users, as it would allow some Debug Mode checks to
>> be enabled in programs that can't currently use it (because
>> recompiling the entire program is not possible).
> ..like this one, which would be a major usability improvement.
>
I'll consider this one, but I fear not for gcc 9.0.

François