In list::sort() we use 65 list objects to use as temporary storage, splicing and swapping elements between lists.
However the lists are default constructed, with no allocator argument, which is wrong because the allocator type might not be default constructible, and even more wrong because splicing and merging between lists with non-equal allocators is undefined behaviour. So if this->get_allocator() != allocator_type() then we have undefined behaviour. The attached patch replaces the fixed-size array of 64 default-constructed lists with a new container-like type, _ListSortBuf, which is initially empty (so we don't create lists we don't need) but will grow up to a maximum size (which I kept at 64). As the container grows it initializes new elements with the correct allocator, so that every list used in the sort uses the same allocator. As well as reducing the number of lists we construct when sorting this also allows us to range-check and ensure we don't overflow the fixed-size array (we now get an exception if that happens, although that's probably not possible even on a 64-bit machine). Unfortunately this seems to hurt performance, presumably the extra indirections to the _ListSOrtBuf rather than just an array of lists confuse the optimisers. Does anyone see any better solution to this? (other than rewriting the whole sort function, which I think has been proposed)
commit ba5b393a09022907f9aee2b539ad14fc1fc8a42d Author: Jonathan Wakely <jwak...@redhat.com> Date: Fri Jul 3 15:20:36 2015 +0100 PR libstdc++/66742 * include/bits/list.tcc (_ListSortBuf): Define. (list::sort): Use _ListSortBuf. * testsuite/23_containers/list/operations/66742.cc: New. diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 714d9b5..f335af4 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -440,6 +440,53 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } } + // A simple array-like container with a fixed maximum size. + template<typename _List, size_t _Size> + class _ListSortBuf + { + template<typename _Tp, typename _Alloc> + friend class list; + + struct __attribute__((__aligned__(__alignof__(_List)))) _Elem + { + unsigned char _M_buf[sizeof(_List)]; + operator _List*() { return reinterpret_cast<_List*>(_M_buf); } + }; + _Elem _M_buf[_Size]; + + typedef typename _List::allocator_type allocator_type; + + struct _Impl : allocator_type + { + _Impl(const allocator_type& __a) : allocator_type(__a), _M_size(0) { } + size_t _M_size; + } _M_impl; + + _ListSortBuf(const allocator_type& __a) : _M_impl(__a) { } + + ~_ListSortBuf() + { + while (_M_impl._M_size) + static_cast<_List*>(_M_buf[--_M_impl._M_size])->~_List(); + } + + _List* begin() { return _M_buf[0]; } + _List* end() { return begin() + _M_impl._M_size; } + + void _M_grow() + { + if (_M_impl._M_size == _Size) + __throw_bad_alloc(); + ::new(static_cast<void*>(_M_buf + _M_impl._M_size)) _List(_M_impl); + ++_M_impl._M_size; + } + + bool empty() const { return _M_impl._M_size == 0; } + + _ListSortBuf(const _ListSortBuf&); + _ListSortBuf& operator=(const _ListSortBuf&); + }; + template<typename _Tp, typename _Alloc> void list<_Tp, _Alloc>:: @@ -448,33 +495,36 @@ _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; + { + list __carry(get_allocator()); + _ListSortBuf<list, 64> __tmp(get_allocator()); + list* __counter; - do - { - __carry.splice(__carry.begin(), *this, begin()); + do + { + __carry.splice(__carry.begin(), *this, begin()); - for(__counter = __tmp; - __counter != __fill && !__counter->empty(); - ++__counter) - { - __counter->merge(__carry); - __carry.swap(*__counter); - } - __carry.swap(*__counter); - if (__counter == __fill) - ++__fill; - } - while ( !empty() ); + for(__counter = __tmp.begin(); + __counter != __tmp.end() && !__counter->empty(); + ++__counter) + { + __counter->merge(__carry); + __carry.swap(*__counter); + } + if (__counter == __tmp.end()) + __tmp._M_grow(); + __carry.swap(*__counter); + } + while ( !empty() ); - for (__counter = __tmp + 1; __counter != __fill; ++__counter) - __counter->merge(*(__counter - 1)); - swap( *(__fill - 1) ); - } + if (!__tmp.empty()) + { + for (__counter = __tmp.begin() + 1; __counter != __tmp.end(); + ++__counter) + __counter->merge(*(__counter - 1)); + swap( *(__tmp.end() - 1) ); + } + } } template<typename _Tp, typename _Alloc> @@ -526,31 +576,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; + list __carry(get_allocator()); + _ListSortBuf<list, 64> __tmp(get_allocator()); + list* __counter; do { __carry.splice(__carry.begin(), *this, begin()); - for(__counter = __tmp; - __counter != __fill && !__counter->empty(); + for(__counter = __tmp.begin(); + __counter != __tmp.end() && !__counter->empty(); ++__counter) { __counter->merge(__carry, __comp); __carry.swap(*__counter); } + if (__counter == __tmp.end()) + __tmp._M_grow(); __carry.swap(*__counter); - if (__counter == __fill) - ++__fill; } while ( !empty() ); - for (__counter = __tmp + 1; __counter != __fill; ++__counter) - __counter->merge(*(__counter - 1), __comp); - swap(*(__fill - 1)); + if (!__tmp.empty()) + { + for (__counter = __tmp.begin() + 1; __counter != __tmp.end(); + ++__counter) + __counter->merge(*(__counter - 1), __comp); + swap( *(__tmp.end() - 1) ); + } } } 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 0000000..252d1d4 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc @@ -0,0 +1,60 @@ +// Copyright (C) 2015 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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++11" } + +#include <list> +#include <testsuite_hooks.h> +#include <testsuite_allocator.h> + +template<typename T> +struct NonDefaultConstructibleAlloc : __gnu_test::SimpleAllocator<T> +{ + NonDefaultConstructibleAlloc(int) { } + + template<typename U> + NonDefaultConstructibleAlloc(const NonDefaultConstructibleAlloc<U>) { } +}; + +void +test01() +{ + using A = NonDefaultConstructibleAlloc<int>; + std::list<int, A> l{ A{1} }; + l.sort(); +} + +void +test02() +{ + using A = __gnu_test::uneq_allocator<int>; + std::list<int, A> l{ A{1} }; + l.push_back(1); + l.push_back(3); + l.push_back(2); + l.sort(); + VERIFY( l.size() == 3 ); + VERIFY( l.front() == 1 ); + VERIFY( l.back() == 3 ); +} + +int +main() +{ + test01(); + test02(); +}