From c2fb0a1a2e7a0fb15cf3cf876f621902ccd273f0 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 12 Aug 2020 20:36:00 +0100 Subject: [PATCH] libstdc++: Make self-move well-defined for containers [PR 85828] The C++ LWG recently confirmed that self-move assignment should not have undefined behaviour for standard containers (see the proposed resolution of LWG 2839). The result should be a valid but unspecified value, just like other times when a container is moved from. Our std::list, std::__cxx11::basic_string and unordered containers all have bugs which result in undefined behaviour. For std::list the problem is that we clear the previous contents using _M_clear() instead of clear(). This means the _M_next, _M_prev and _M_size members are not zeroed, and so after we "update" them (with their existing values), we are left with dangling pointers and a non-zero size, but no elements. For the unordered containers the problem is similar. _Hashtable first deallocates the existing contents, then takes ownership of the pointers from the RHS object (which has just had its contents deallocated so the pointers are dangling). For std::basic_string it's a little more subtle. When the string is local (i.e. fits in the SSO buffer) we use char_traits::copy to copy the contents from this->data() to __rhs.data(). When &__rhs == this that copy violates the precondition that the ranges don't overlap. We only need to check for self-move for this case where it's local, because the only other case that can be true for self-move is that it's non-local but the allocators compare equal. In that case the data pointer is neither deallocated nor leaked, so the result is well-defined. This patch also makes a small optimization for std::deque move assignment, to use the efficient move when is_always_equal is false, but the allocators compare equal at runtime. Finally, we need to remove all the Debug Mode checks which abort the program when a self-move is detected, because it's not undefined to do that. Before PR 85828 can be closed we should also look into fixing std::shuffle so it doesn't do any redundant self-swaps. libstdc++-v3/ChangeLog: PR libstdc++/85828 * include/bits/basic_string.h (operator=(basic_string&&)): Check for self-move before copying with char_traits::copy. * include/bits/hashtable.h (operator=(_Hashtable&&)): Check for self-move. * include/bits/stl_deque.h (_M_move_assign1(deque&&, false_type)): Check for equal allocators. * include/bits/stl_list.h (_M_move_assign(list&&, true_type)): Call clear() instead of _M_clear(). * include/debug/formatter.h (__msg_self_move_assign): Change comment. * include/debug/macros.h (__glibcxx_check_self_move_assign): (_GLIBCXX_DEBUG_VERIFY): Remove. * include/debug/safe_container.h (operator=(_Safe_container&&)): Remove assertion check for safe move and make it well-defined. * include/debug/safe_iterator.h (operator=(_Safe_iterator&&)): Remove assertion check for self-move. * include/debug/safe_local_iterator.h (operator=(_Safe_local_iterator&&)): Likewise. * testsuite/21_strings/basic_string/cons/char/self_move.cc: New test. * testsuite/23_containers/deque/cons/self_move.cc: New test. * testsuite/23_containers/forward_list/cons/self_move.cc: New test. * testsuite/23_containers/list/cons/self_move.cc: New test. * testsuite/23_containers/set/cons/self_move.cc: New test. * testsuite/23_containers/unordered_set/cons/self_move.cc: New test. * testsuite/23_containers/vector/cons/self_move.cc: New test. --- libstdc++-v3/include/bits/basic_string.h | 13 +++-- libstdc++-v3/include/bits/hashtable.h | 3 ++ libstdc++-v3/include/bits/stl_deque.h | 3 ++ libstdc++-v3/include/bits/stl_list.h | 2 +- libstdc++-v3/include/debug/formatter.h | 2 +- libstdc++-v3/include/debug/macros.h | 6 --- libstdc++-v3/include/debug/safe_container.h | 9 +++- libstdc++-v3/include/debug/safe_iterator.h | 6 +-- .../include/debug/safe_local_iterator.h | 6 +-- .../basic_string/cons/char/self_move.cc | 52 +++++++++++++++++++ .../23_containers/deque/cons/self_move.cc | 44 ++++++++++++++++ .../forward_list/cons/self_move.cc | 44 ++++++++++++++++ .../23_containers/list/cons/self_move.cc | 44 ++++++++++++++++ .../23_containers/set/cons/self_move.cc | 47 +++++++++++++++++ .../unordered_set/cons/self_move.cc | 50 ++++++++++++++++++ .../23_containers/vector/cons/self_move.cc | 44 ++++++++++++++++ 16 files changed, 356 insertions(+), 19 deletions(-) create mode 100644 libstdc++-v3/testsuite/21_strings/basic_string/cons/char/self_move.cc create mode 100644 libstdc++-v3/testsuite/23_containers/deque/cons/self_move.cc create mode 100644 libstdc++-v3/testsuite/23_containers/forward_list/cons/self_move.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list/cons/self_move.cc create mode 100644 libstdc++-v3/testsuite/23_containers/set/cons/self_move.cc create mode 100644 libstdc++-v3/testsuite/23_containers/unordered_set/cons/self_move.cc create mode 100644 libstdc++-v3/testsuite/23_containers/vector/cons/self_move.cc diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h index e34b5c1fca3..a9fe09f2069 100644 --- a/libstdc++-v3/include/bits/basic_string.h +++ b/libstdc++-v3/include/bits/basic_string.h @@ -717,10 +717,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 if (__str._M_is_local()) { - // We've always got room for a short string, just copy it. - if (__str.size()) - this->_S_copy(_M_data(), __str._M_data(), __str.size()); - _M_set_length(__str.size()); + // We've always got room for a short string, just copy it + // (unless this is a self-move, because that would violate the + // char_traits::copy precondition that the ranges don't overlap). + if (__builtin_expect(std::__addressof(__str) != this, true)) + { + if (__str.size()) + this->_S_copy(_M_data(), __str._M_data(), __str.size()); + _M_set_length(__str.size()); + } } else if (_Alloc_traits::_S_propagate_on_move_assign() || _Alloc_traits::_S_always_equal() diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index dc8ed2ee18c..7b772a475e3 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1296,6 +1296,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_move_assign(_Hashtable&& __ht, true_type) { + if (__builtin_expect(std::__addressof(__ht) == this, false)) + return; + this->_M_deallocate_nodes(_M_begin()); _M_deallocate_buckets(); __hashtable_base::operator=(std::move(__ht)); diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index 3959dd7899d..baebf7a343b 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -2156,6 +2156,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void _M_move_assign1(deque&& __x, /* always equal: */ false_type) { + if (_M_get_Tp_allocator() == __x._M_get_Tp_allocator()) + return _M_move_assign1(std::move(__x), true_type()); + constexpr bool __move_storage = _Alloc_traits::_S_propagate_on_move_assign(); _M_move_assign2(std::move(__x), __bool_constant<__move_storage>()); diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index e7135e3e7ed..d63a96562e0 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -1947,7 +1947,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 void _M_move_assign(list&& __x, true_type) noexcept { - this->_M_clear(); + this->clear(); this->_M_move_nodes(std::move(__x)); std::__alloc_on_move(this->_M_get_Node_allocator(), __x._M_get_Node_allocator()); diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h index bb9b3e5653a..c4283fe6047 100644 --- a/libstdc++-v3/include/debug/formatter.h +++ b/libstdc++-v3/include/debug/formatter.h @@ -143,7 +143,7 @@ namespace __gnu_debug // unordered container local iterators __msg_local_iter_compare_bad, __msg_non_empty_range, - // self move assign + // self move assign (no longer used) __msg_self_move_assign, // unordered container buckets __msg_bucket_index_oob, diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h index 73fb50d0cbd..ed606809a4d 100644 --- a/libstdc++-v3/include/debug/macros.h +++ b/libstdc++-v3/include/debug/macros.h @@ -447,12 +447,6 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_partitioned_upper( \ ._M_iterator(_Last, #_Last) \ ._M_string(#_Pred)) -// Verify that the container is not self move assigned -#define __glibcxx_check_self_move_assign(_Other) \ -_GLIBCXX_DEBUG_VERIFY(this != &_Other, \ - _M_message(__gnu_debug::__msg_self_move_assign) \ - ._M_sequence(*this, "this")) - // Verify that load factor is positive #define __glibcxx_check_max_load_factor(_F) \ _GLIBCXX_DEBUG_VERIFY(_F > 0.0f, \ diff --git a/libstdc++-v3/include/debug/safe_container.h b/libstdc++-v3/include/debug/safe_container.h index 36b3e017c19..2059eca9855 100644 --- a/libstdc++-v3/include/debug/safe_container.h +++ b/libstdc++-v3/include/debug/safe_container.h @@ -80,7 +80,14 @@ namespace __gnu_debug _Safe_container& operator=(_Safe_container&& __x) noexcept { - __glibcxx_check_self_move_assign(__x); + if (std::__addressof(__x) == this) + { + // Standard containers have a valid but unspecified value after + // self-move, so we invalidate all debug iterators even if the + // underlying container happens to preserve its contents. + this->_M_invalidate_all(); + return *this; + } if (_IsCxx11AllocatorAware) { diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index 687b844fd75..84a9f1d526d 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -263,15 +263,15 @@ namespace __gnu_debug _Safe_iterator& operator=(_Safe_iterator&& __x) noexcept { - _GLIBCXX_DEBUG_VERIFY(this != &__x, - _M_message(__msg_self_move_assign) - ._M_iterator(*this, "this")); _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() || __x.base() == _Iterator(), _M_message(__msg_copy_singular) ._M_iterator(*this, "this") ._M_iterator(__x, "other")); + if (std::__addressof(__x) == this) + return *this; + if (this->_M_sequence && this->_M_sequence == __x._M_sequence) { __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h index d0abcf6da24..5b051d0ebf9 100644 --- a/libstdc++-v3/include/debug/safe_local_iterator.h +++ b/libstdc++-v3/include/debug/safe_local_iterator.h @@ -209,15 +209,15 @@ namespace __gnu_debug _Safe_local_iterator& operator=(_Safe_local_iterator&& __x) noexcept { - _GLIBCXX_DEBUG_VERIFY(this != &__x, - _M_message(__msg_self_move_assign) - ._M_iterator(*this, "this")); _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() || __x.base() == _Iterator(), _M_message(__msg_copy_singular) ._M_iterator(*this, "this") ._M_iterator(__x, "other")); + if (std::__addressof(__x) == this) + return *this; + if (this->_M_sequence && this->_M_sequence == __x._M_sequence) { __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/self_move.cc b/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/self_move.cc new file mode 100644 index 00000000000..456b03353c3 --- /dev/null +++ b/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/self_move.cc @@ -0,0 +1,52 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } + +#include +#include +#include + +template +void +test(const char* s) +{ + String s1 = s; + std::string s2 __attribute__((unused)) = s1.c_str(); + s1 = std::move(s1); + + String s3 __attribute__((unused)) = s1; + s1 = std::move(s1); + + s1.begin(); // causes COW string to "leak" + s1 = std::move(s1); + + String s4 __attribute__((unused)) = s1; + s1 = std::move(s1); + + s1.reserve(2 * s1.capacity()); // causes SSO string to be on the heap + s1 = std::move(s1); +} + +int +main() +{ + test("short"); + test("very, very, very, VERY long"); + test<__gnu_debug::string>("short"); + test<__gnu_debug::string>("very, very, very, VERY long"); +} diff --git a/libstdc++-v3/testsuite/23_containers/deque/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/deque/cons/self_move.cc new file mode 100644 index 00000000000..e05f43c572f --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/deque/cons/self_move.cc @@ -0,0 +1,44 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } + +#include +#include +#include + +template +void +test(std::initializer_list vals) +{ + Container c{vals}; + c = std::move(c); + VERIFY( c == c ); + + auto it = c.begin(); + it = std::move(it); + VERIFY( it == c.begin() ); +} + +int +main() +{ + test>({1, 2, 3}); + test>>({{1,2}, {3,4}, {5,6}, {7,8}}); + test<__gnu_debug::deque>({1, 2, 3}); + test<__gnu_debug::deque>>({{1,2}, {3,4}}); +} diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/forward_list/cons/self_move.cc new file mode 100644 index 00000000000..35525cab263 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/cons/self_move.cc @@ -0,0 +1,44 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } + +#include +#include +#include + +template +void +test(std::initializer_list vals) +{ + Container c{vals}; + c = std::move(c); + VERIFY( c == c ); + + auto it = c.begin(); + it = std::move(it); + VERIFY( it == c.begin() ); +} + +int +main() +{ + test>({1, 2, 3}); + test>>({{1,2}, {3,4}, {5,6}, {7,8}}); + test<__gnu_debug::forward_list>({1, 2, 3}); + test<__gnu_debug::forward_list>>({{1,2}, {3,4}}); +} diff --git a/libstdc++-v3/testsuite/23_containers/list/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/list/cons/self_move.cc new file mode 100644 index 00000000000..6ff6f1527e7 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/cons/self_move.cc @@ -0,0 +1,44 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } + +#include +#include +#include + +template +void +test(std::initializer_list vals) +{ + Container c{vals}; + c = std::move(c); + VERIFY( c == c ); + + auto it = c.begin(); + it = std::move(it); + VERIFY( it == c.begin() ); +} + +int +main() +{ + test>({1, 2, 3}); + test>>({{1,2}, {3,4}, {5,6}, {7,8}}); + test<__gnu_debug::list>({1, 2, 3}); + test<__gnu_debug::list>>({{1,2}, {3,4}}); +} diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/set/cons/self_move.cc new file mode 100644 index 00000000000..9c226622ae6 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/set/cons/self_move.cc @@ -0,0 +1,47 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } + +#include +#include +#include +#include +#include + +template +void +test(std::initializer_list vals) +{ + Container c{vals}; + c = std::move(c); + VERIFY( c == c ); + + auto it = c.begin(); + it = std::move(it); + VERIFY( it == c.begin() ); +} + +int +main() +{ + std::string s = "how long is a piece of SSO string?"; + test>({1, 2, 3}); + test>({s, s, s, s}); + test<__gnu_debug::set>({1, 2, 3}); + test<__gnu_debug::set>({s, s, s, s}); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/self_move.cc new file mode 100644 index 00000000000..089f2c07b88 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/self_move.cc @@ -0,0 +1,50 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } + +#include +#include +#include +#include +#include + +template +void +test(std::initializer_list vals) +{ + Container c{vals}; + c = std::move(c); + VERIFY( c == c ); + + auto it = c.begin(); + it = std::move(it); + VERIFY( it == c.begin() ); + + auto localit = c.begin(0); + localit = std::move(localit); +} + +int +main() +{ + std::string s = "how long is a piece of SSO string?"; + test>({1, 2, 3}); + test>({s, s, s, s}); + test<__gnu_debug::unordered_set>({1, 2, 3}); + test<__gnu_debug::unordered_set>({s, s, s, s}); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/cons/self_move.cc b/libstdc++-v3/testsuite/23_containers/vector/cons/self_move.cc new file mode 100644 index 00000000000..02159ee6293 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/cons/self_move.cc @@ -0,0 +1,44 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-do run { target c++11 } } + +#include +#include +#include + +template +void +test(std::initializer_list vals) +{ + Container c{vals}; + c = std::move(c); + VERIFY( c == c ); + + auto it = c.begin(); + it = std::move(it); + VERIFY( it == c.begin() ); +} + +int +main() +{ + test>({1, 2, 3}); + test>>({{1,2}, {3,4}, {5,6}, {7,8}}); + test<__gnu_debug::vector>({1, 2, 3}); + test<__gnu_debug::vector>>({{1,2}, {3,4}}); +} -- 2.30.2