Message ID | 2058d369-69a9-e4ad-a4d0-147277bd766a@gmail.com |
---|---|
State | New |
Headers | show |
Series | Improve safe iterator move semantic | expand |
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
diff --git a/libstdc++-v3/config/abi/pre/gnu.ver b/libstdc++-v3/config/abi/pre/gnu.ver index 593783d..1143d9a 100644 --- a/libstdc++-v3/config/abi/pre/gnu.ver +++ b/libstdc++-v3/config/abi/pre/gnu.ver @@ -2046,6 +2046,7 @@ GLIBCXX_3.4.26 { _ZNSt3pmr25monotonic_buffer_resource13_M_new_bufferE[jmy][jmy]; _ZNSt3pmr25monotonic_buffer_resource18_M_release_buffersEv; + _ZN11__gnu_debug25_Safe_local_iterator_base16_M_detach_singleEv; } GLIBCXX_3.4.25; # Symbols in the support library (libsupc++) have their own tag. diff --git a/libstdc++-v3/include/debug/safe_base.h b/libstdc++-v3/include/debug/safe_base.h index f58a78f..c276a18 100644 --- a/libstdc++-v3/include/debug/safe_base.h +++ b/libstdc++-v3/include/debug/safe_base.h @@ -97,6 +97,13 @@ 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. */ @@ -121,6 +128,12 @@ namespace __gnu_debug void _M_detach(); +#if __cplusplus >= 201103L + /** Attaches this iterator at __x place. */ + void + _M_move_to(_Safe_iterator_base* __x, bool __constant); +#endif + public: /** Likewise, but not thread-safe. */ void @@ -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)); } /** Unlink itself */ void - _M_unlink() throw () + _M_unlink() _GLIBCXX_USE_NOEXCEPT { if (_M_prior) _M_prior->_M_next = _M_next; @@ -273,6 +287,28 @@ namespace __gnu_debug void _M_detach_single(_Safe_iterator_base* __it) throw (); }; + +#if __cplusplus >= 201103L + inline void + _Safe_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_sequence->_M_const_iterators : _M_sequence->_M_iterators; + if (__its == __x) + __its = this; + } + + if (_M_next) + _M_next->_M_prior = this; + } +#endif + } // namespace __gnu_debug #endif diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index b8256fc..4b5773f 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -151,17 +151,20 @@ namespace __gnu_debug * @post __x is singular and unattached */ _Safe_iterator(_Safe_iterator&& __x) noexcept - : _Iter_base() + : _Iter_base(__x), _Safe_base(std::move(__x)) { _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() || __x.base() == _Iterator(), _M_message(__msg_init_copy_singular) ._M_iterator(*this, "this") ._M_iterator(__x, "other")); - _Safe_sequence_base* __seq = __x._M_sequence; - __x._M_detach(); - std::swap(base(), __x.base()); - _M_attach(__seq); + if (__x._M_sequence) + { + _M_move_to(&__x, _S_constant()); + + __x._M_reset(); + __x.base() = _Iter_base(); + } } #endif @@ -238,16 +241,22 @@ namespace __gnu_debug { __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); base() = __x.base(); - _M_version = __x._M_sequence->_M_version; + _M_version = __x._M_version; + __x._M_detach_single(); } else { _M_detach(); base() = __x.base(); - _M_attach(__x._M_sequence); + + if (__x._M_sequence) + { + _Safe_base::operator=(std::move(__x)); + _M_move_to(&__x, _S_constant()); + __x._M_reset(); + } } - __x._M_detach(); __x.base() = _Iterator(); return *this; } diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h index f9597a6..2dd9a19 100644 --- a/libstdc++-v3/include/debug/safe_local_iterator.h +++ b/libstdc++-v3/include/debug/safe_local_iterator.h @@ -112,17 +112,20 @@ namespace __gnu_debug * @post __x is singular and unattached */ _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept - : _Iter_base() + : _Iter_base(__x), _Safe_base(std::move(__x)) { _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); + if (__x._M_sequence) + { + _M_move_to(&__x, _S_constant()); + + __x._M_reset(); + __x.base() = _Iter_base(); + } } /** @@ -198,16 +201,22 @@ namespace __gnu_debug { __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); base() = __x.base(); - _M_version = __x._M_sequence->_M_version; + _M_version = __x._M_version; + __x._M_detach_single(); } else { _M_detach(); base() = __x.base(); - _M_attach(__x._M_sequence); + + if (__x._M_sequence) + { + _Safe_base::operator=(std::move(__x)); + _M_move_to(&__x, _S_constant()); + __x._M_reset(); + } } - __x._M_detach(); __x.base() = _Iterator(); return *this; } diff --git a/libstdc++-v3/include/debug/safe_unordered_base.h b/libstdc++-v3/include/debug/safe_unordered_base.h index 5dd0e0e..340aea6 100644 --- a/libstdc++-v3/include/debug/safe_unordered_base.h +++ b/libstdc++-v3/include/debug/safe_unordered_base.h @@ -51,8 +51,9 @@ namespace __gnu_debug { protected: /** Initializes the iterator and makes it singular. */ - _Safe_local_iterator_base() - { } + _Safe_local_iterator_base() = default; + + _Safe_local_iterator_base(_Safe_local_iterator_base&&) = default; /** Initialize the iterator to reference the container pointed to * by @p __seq. @p __constant is true when we are initializing a @@ -62,17 +63,20 @@ namespace __gnu_debug * be nonsingular. */ _Safe_local_iterator_base(const _Safe_sequence_base* __seq, bool __constant) - { this->_M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); } + { _M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); } /** Initializes the iterator to reference the same container that @p __x does. @p __constant is true if this is a constant iterator, and false if it is mutable. */ _Safe_local_iterator_base(const _Safe_local_iterator_base& __x, bool __constant) - { this->_M_attach(__x._M_sequence, __constant); } + { _M_attach(__x._M_sequence, __constant); } ~_Safe_local_iterator_base() { this->_M_detach(); } + _Safe_local_iterator_base& + operator=(_Safe_local_iterator_base&&) = default; + _Safe_unordered_container_base* _M_get_container() const noexcept; @@ -97,6 +101,10 @@ namespace __gnu_debug /** Likewise, but not thread-safe. */ void _M_detach_single() throw (); + + /** Attaches this iterator at __x place. */ + void + _M_move_to(_Safe_iterator_base* __x, bool __constant); }; /** @@ -180,6 +188,31 @@ namespace __gnu_debug void _M_detach_local_single(_Safe_iterator_base* __it) throw (); }; + + inline _Safe_unordered_container_base* + _Safe_local_iterator_base::_M_get_container() const noexcept + { return static_cast<_Safe_unordered_container_base*>(_M_sequence); } + + 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; + } } // namespace __gnu_debug #endif diff --git a/libstdc++-v3/src/c++11/debug.cc b/libstdc++-v3/src/c++11/debug.cc index 3cae3db..8edbfc0 100644 --- a/libstdc++-v3/src/c++11/debug.cc +++ b/libstdc++-v3/src/c++11/debug.cc @@ -401,16 +401,6 @@ namespace __gnu_debug } } - void - _Safe_iterator_base:: - _M_reset() throw () - { - _M_sequence = 0; - _M_version = 0; - _M_prior = 0; - _M_next = 0; - } - bool _Safe_iterator_base:: _M_singular() const throw () @@ -429,11 +419,6 @@ namespace __gnu_debug _M_get_mutex() throw () { return _M_sequence->_M_get_mutex(); } - _Safe_unordered_container_base* - _Safe_local_iterator_base:: - _M_get_container() const noexcept - { return static_cast<_Safe_unordered_container_base*>(_M_sequence); } - void _Safe_local_iterator_base:: _M_attach(_Safe_sequence_base* __cont, bool __constant)