From patchwork Fri Oct 1 19:43:58 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 1535534 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=RSJkYTLT; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4HLhLz0NHzz9t25 for ; Sat, 2 Oct 2021 06:20:41 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2E4B53857005 for ; Fri, 1 Oct 2021 20:20:39 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2E4B53857005 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1633119639; bh=ed8x3yhfdLJPlgbZTajT5udDA1ZQhssqQM2wqJlhqKk=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=RSJkYTLTnwXvHiHM8tJWmeTpt/GJOgQ0mIHejQISnmch6orV2bf/ew4gxOsD0LmXA hGeFhe/6CJV5D+sW69SzYDvQUhsXCtQW1vHAUsOvZlu+PPn3CwxCeqOkVwRGsnOGyJ yfNk7O0dajPxxYxqGCkE95I1eFlHrGogkSkvjG8g= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 91D4B385781C for ; Fri, 1 Oct 2021 19:44:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 91D4B385781C Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-238-CalR1yAsOTGpgheYOgkk_w-1; Fri, 01 Oct 2021 15:44:01 -0400 X-MC-Unique: CalR1yAsOTGpgheYOgkk_w-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 46C28362F9; Fri, 1 Oct 2021 19:44:00 +0000 (UTC) Received: from localhost (unknown [10.33.36.47]) by smtp.corp.redhat.com (Postfix) with ESMTP id C131D5DF26; Fri, 1 Oct 2021 19:43:59 +0000 (UTC) Date: Fri, 1 Oct 2021 20:43:58 +0100 To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Allow stateful allocators in std::list::sort [PR 66742] Message-ID: MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Jonathan Wakely via Gcc-patches From: Jonathan Wakely Reply-To: Jonathan Wakely Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" The temporary lists used by std::list::sort are default constructed, which means they use default constructed allocators. The sort operation is defined in terms of merge and splice operations, which have undefined behaviour (and abort) if the allocators do not compare equal. This means it is not possible to sort a list that uses an allocator that compares unequal to an default constructed allocator. The solution is to avoid using temporary std::list objects at all. We do not need to be able to allocate memory because no nodes are allocated, only spliced from one list to another. That means the temporary lists don't need an allocator at all, so whether it would compare equal doesn't matter. Instead of temporary std::list objects, we can just use a collection of _List_node_base objects that nodes can be spliced onto as needed. Those objects are wrapped in a _Scratch_list type that implements the splicing and merging operations used by list::sort. We also don't need to update the list size during the sort, because sorting doesn't alter the number of nodes. Although we move nodes in and out of the scratch lists, at the end of the function all nodes are back in the original std::list and the scratch lists are empty. So for the cxx11 ABI we can avoid the _M_size modifications usually done when splicing nodes. Signed-off-by: Jonathan Wakely libstdc++-v3/ChangeLog: PR libstdc++/66742 * include/bits/list.tcc (list::sort()): Use _Scratch_list objects for splicing and merging. (list::sort(StrictWeakOrdering)): Likewise. * include/bits/stl_list.h (__detail::_Scratch_list): New type. * src/c++98/list.cc (_List_node_base::_M_transfer): Add assertion for --enable-libstdcxx-debug library. * testsuite/23_containers/list/operations/66742.cc: New test. Tested powerpc64le-linux. Committed to trunk. commit ff7793bea465019683b3a07d7ffceb6eae22def5 Author: Jonathan Wakely Date: Tue May 25 14:33:15 2021 libstdc++: Allow stateful allocators in std::list::sort [PR 66742] The temporary lists used by std::list::sort are default constructed, which means they use default constructed allocators. The sort operation is defined in terms of merge and splice operations, which have undefined behaviour (and abort) if the allocators do not compare equal. This means it is not possible to sort a list that uses an allocator that compares unequal to an default constructed allocator. The solution is to avoid using temporary std::list objects at all. We do not need to be able to allocate memory because no nodes are allocated, only spliced from one list to another. That means the temporary lists don't need an allocator at all, so whether it would compare equal doesn't matter. Instead of temporary std::list objects, we can just use a collection of _List_node_base objects that nodes can be spliced onto as needed. Those objects are wrapped in a _Scratch_list type that implements the splicing and merging operations used by list::sort. We also don't need to update the list size during the sort, because sorting doesn't alter the number of nodes. Although we move nodes in and out of the scratch lists, at the end of the function all nodes are back in the original std::list and the scratch lists are empty. So for the cxx11 ABI we can avoid the _M_size modifications usually done when splicing nodes. Signed-off-by: Jonathan Wakely libstdc++-v3/ChangeLog: PR libstdc++/66742 * include/bits/list.tcc (list::sort()): Use _Scratch_list objects for splicing and merging. (list::sort(StrictWeakOrdering)): Likewise. * include/bits/stl_list.h (__detail::_Scratch_list): New type. * src/c++98/list.cc (_List_node_base::_M_transfer): Add assertion for --enable-libstdcxx-debug library. * testsuite/23_containers/list/operations/66742.cc: New test. diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 62b0ba1063a..7f4e1569ab1 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -485,21 +485,34 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) { - list __carry; - list __tmp[64]; - list * __fill = __tmp; - list * __counter; + using __detail::_Scratch_list; + // The algorithm used here is largely unchanged from the SGI STL + // and is described in The C++ Standard Template Library by Plauger, + // Stepanov, Lee, Musser. + // Each element of *this is spliced out and merged into one of the + // sorted lists in __tmp, then all the lists in __tmp are merged + // together and then swapped back into *this. + // Because all nodes end up back in *this we do not need to update + // this->size() while nodes are temporarily moved out. + _Scratch_list __carry; + _Scratch_list __tmp[64]; + _Scratch_list* __fill = __tmp; + _Scratch_list* __counter; + + _Scratch_list::_Ptr_cmp __ptr_comp; + __try { do { - __carry.splice(__carry.begin(), *this, begin()); + __carry._M_take_one(begin()._M_node); for(__counter = __tmp; __counter != __fill && !__counter->empty(); ++__counter) { - __counter->merge(__carry); + + __counter->merge(__carry, __ptr_comp); __carry.swap(*__counter); } __carry.swap(*__counter); @@ -509,14 +522,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER while ( !empty() ); for (__counter = __tmp + 1; __counter != __fill; ++__counter) - __counter->merge(*(__counter - 1)); - swap( *(__fill - 1) ); + __counter->merge(__counter[-1], __ptr_comp); + __fill[-1].swap(this->_M_impl._M_node); } __catch(...) { - this->splice(this->end(), __carry); + // Move all nodes back into *this. + __carry._M_put_all(end()._M_node); for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) - this->splice(this->end(), __tmp[__i]); + __tmp[__i]._M_put_all(end()._M_node); __throw_exception_again; } } @@ -602,42 +616,49 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Do nothing if the list has length 0 or 1. if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) - { - list __carry; - list __tmp[64]; - list * __fill = __tmp; - list * __counter; - __try - { - do - { - __carry.splice(__carry.begin(), *this, begin()); + { + using __detail::_Scratch_list; + _Scratch_list __carry; + _Scratch_list __tmp[64]; + _Scratch_list* __fill = __tmp; + _Scratch_list* __counter; - for(__counter = __tmp; - __counter != __fill && !__counter->empty(); - ++__counter) - { - __counter->merge(__carry, __comp); - __carry.swap(*__counter); - } - __carry.swap(*__counter); - if (__counter == __fill) - ++__fill; - } - while ( !empty() ); + _Scratch_list::_Ptr_cmp __ptr_comp + = { __comp }; - for (__counter = __tmp + 1; __counter != __fill; ++__counter) - __counter->merge(*(__counter - 1), __comp); - swap(*(__fill - 1)); - } - __catch(...) - { - this->splice(this->end(), __carry); - for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) - this->splice(this->end(), __tmp[__i]); - __throw_exception_again; - } - } + __try + { + do + { + __carry._M_take_one(begin()._M_node); + + for(__counter = __tmp; + __counter != __fill && !__counter->empty(); + ++__counter) + { + + __counter->merge(__carry, __ptr_comp); + __carry.swap(*__counter); + } + __carry.swap(*__counter); + if (__counter == __fill) + ++__fill; + } + while ( !empty() ); + + for (__counter = __tmp + 1; __counter != __fill; ++__counter) + __counter->merge(__counter[-1], __ptr_comp); + __fill[-1].swap(this->_M_impl._M_node); + } + __catch(...) + { + // Move all nodes back into *this. + __carry._M_put_all(end()._M_node); + for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) + __tmp[__i]._M_put_all(end()._M_node); + __throw_exception_again; + } + } } _GLIBCXX_END_NAMESPACE_CONTAINER diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index e11603c0157..81361dfa4d5 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -158,6 +158,73 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: _List_node_base* _M_base() { return this; } }; + + // Used by list::sort to hold nodes being sorted. + struct _Scratch_list : _List_node_base + { + _Scratch_list() { _M_next = _M_prev = this; } + + bool empty() const { return _M_next == this; } + + void swap(_List_node_base& __l) { _List_node_base::swap(*this, __l); } + + template + struct _Ptr_cmp + { + _Cmp _M_cmp; + + bool + operator()(const __detail::_List_node_base* __lhs, + const __detail::_List_node_base* __rhs) /* not const */ + { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); } + }; + + template + struct _Ptr_cmp<_Iter, void> + { + bool + operator()(const __detail::_List_node_base* __lhs, + const __detail::_List_node_base* __rhs) const + { return *_Iter(__lhs) < *_Iter(__rhs); } + }; + + // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp. + template + void + merge(_List_node_base& __x, _Cmp __comp) + { + _List_node_base* __first1 = _M_next; + _List_node_base* const __last1 = this; + _List_node_base* __first2 = __x._M_next; + _List_node_base* const __last2 = std::__addressof(__x); + + while (__first1 != __last1 && __first2 != __last2) + { + if (__comp(__first2, __first1)) + { + _List_node_base* __next = __first2->_M_next; + __first1->_M_transfer(__first2, __next); + __first2 = __next; + } + else + __first1 = __first1->_M_next; + } + if (__first2 != __last2) + this->_M_transfer(__first2, __last2); + } + + // Splice the node at __i into *this. + void _M_take_one(_List_node_base* __i) + { this->_M_transfer(__i, __i->_M_next); } + + // Splice all nodes from *this after __i. + void _M_put_all(_List_node_base* __i) + { + if (!empty()) + __i->_M_transfer(_M_next, this); + } + }; + } // namespace detail _GLIBCXX_BEGIN_NAMESPACE_CONTAINER diff --git a/libstdc++-v3/src/c++98/list.cc b/libstdc++-v3/src/c++98/list.cc index 18f0e136c47..c2f5c43622e 100644 --- a/libstdc++-v3/src/c++98/list.cc +++ b/libstdc++-v3/src/c++98/list.cc @@ -94,6 +94,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_transfer(_List_node_base * const __first, _List_node_base * const __last) _GLIBCXX_USE_NOEXCEPT { + __glibcxx_assert(__first != __last); + if (this != __last) { // Remove [first, last) from its old position. diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc new file mode 100644 index 00000000000..24bda3920d8 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc @@ -0,0 +1,55 @@ +// { dg-do run { target c++11 } } + +#include +#include +#include + +// PR libstdc++/66742 +// abort on sorting list with custom allocator that is not stateless + +template> +bool is_sorted(const List& l, Cmp cmp = {}) +{ + auto it = l.begin(); + auto next = it; + const auto end = l.end(); + if (it == end) + return true; + while (++next != end) + if (cmp(*next, *it)) + return false; + else + it = next; + return true; +} + +void +test01() +{ + using Alloc = __gnu_test::uneq_allocator; + Alloc a1(1); + std::list l(a1); + for (int i = 0; i < 1000; ++i) + { + l.push_front(i); + l.push_back(i + (i % 3)); + } + const auto orig = l; + + l.sort(); + VERIFY( is_sorted(l) ); + l.sort(); + VERIFY( is_sorted(l) ); + + l = orig; + l.sort(std::less()); + VERIFY( is_sorted(l) ); + l.sort(std::greater()); + VERIFY( is_sorted(l, std::greater()) ); +} + +int +main() +{ + test01(); +}