[PATH][_GLIBCXX_DEBUG] Fix unordered container merge
François Dumont
frs.dumont@gmail.com
Wed Nov 10 05:44:55 GMT 2021
I can't see any clue on how my commit can have had an impact on below code.
I don't think libstdc++ hash table has any relation with gcc hash table.
Still, I'm rebuilding gcc at my revision to confirm.
On 10/11/21 1:05 am, H.J. Lu wrote:
> On Mon, Nov 8, 2021 at 1:37 PM François Dumont via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> Yet another version this time with only 1 guard implementation. The
>> predicate to invalidate the safe iterators has been externalized.
>>
>> Ok to commit ?
>>
> This may have broken GCC bootstrap on Linux/x86-64:
>
> https://gcc.gnu.org/pipermail/gcc-regression/2021-November/075734.html
>
> In file included from ../../src-master/gcc/sanopt.c:22:
> In member function ‘hash_table<Descriptor, Lazy,
> Allocator>::value_type* hash_table<Descriptor, Lazy,
> Allocator>::alloc_entries(size_t) const [with Descriptor =
> hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> false; Allocator = xcallocator]’,
> inlined from ‘void hash_table<Descriptor, Lazy,
> Allocator>::expand() [with Descriptor = hash_map<tree_node*,
> auto_vec<gimple*> >::hash_entry; bool Lazy = false; Allocator =
> xcallocator]’ at ../../src-master/gcc/hash-table.h:802:40:
> ../../src-master/gcc/system.h:784:34: error: section type conflict
> with ‘void hash_table<Descriptor, Lazy, Allocator>::expand() [with
> Descriptor = hash_map<tree_node*, auto_vec<gimple*> >::hash_entry;
> bool Lazy = false; Allocator = xcallocator]’
> 784 | ((void)(!(EXPR) ? fancy_abort (__FILE__, __LINE__,
> __FUNCTION__), 0 : 0))
> | ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> ../../src-master/gcc/hash-table.h:715:3: note: in expansion of macro
> ‘gcc_assert’
> 715 | gcc_assert (nentries != NULL);
> | ^~~~~~~~~~
> In file included from ../../src-master/gcc/coretypes.h:482,
> from ../../src-master/gcc/sanopt.c:23:
> ../../src-master/gcc/hash-table.h: In member function ‘void
> hash_table<Descriptor, Lazy, Allocator>::expand() [with Descriptor =
> hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> false; Allocator = xcallocator]’:
> ../../src-master/gcc/hash-table.h:779:1: note: ‘void
> hash_table<Descriptor, Lazy, Allocator>::expand() [with Descriptor =
> hash_map<tree_node*, auto_vec<gimple*> >::hash_entry; bool Lazy =
> false; Allocator = xcallocator]’ was declared here
> 779 | hash_table<Descriptor, Lazy, Allocator>::expand ()
> | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
>> On 06/11/21 2:51 pm, François Dumont wrote:
>>> You were right to delay your reply. Here is a new version with less
>>> code duplication and a bug fix in the new _UContMergeGuard where we
>>> were using it->second rather than it->first to get the key.
>>>
>>> Note also that the change to _M_merge_multi implementation is also
>>> important because otherwise we might be trying to extract a key from a
>>> destructed node.
>>>
>>> libstdc++: [_GLIBCXX_DEBUG] Implement unordered container merge
>>>
>>> The _GLIBCXX_DEBUG unordered containers need a dedicated merge
>>> implementation
>>> so that any existing iterator on the transfered nodes is properly
>>> invalidated.
>>>
>>> Add typedef/using declaration for everything used as-is from
>>> normal implementation.
>>>
>>> libstdc++-v3/ChangeLog:
>>>
>>> * include/bits/hashtable_policy.h (__distance_fw): Replace
>>> class keyword with
>>> typename.
>>> * include/bits/hashtable.h
>>> (_Hashtable<>::_M_merge_unique): Remove noexcept
>>> qualification. Use const_iterator for node
>>> extraction/reinsert.
>>> (_Hashtable<>::_M_merge_multi): Likewise. Compute new hash
>>> code before extract.
>>> * include/debug/safe_container.h (_Safe_container<>): Make
>>> all methods
>>> protected.
>>> * include/debug/safe_unordered_container.h
>>> (_Safe_unordered_container<>::_UContMergeGuard<_ExtractKey, _Source>):
>>> New.
>>> (_Safe_unordered_container<>::_S_uc_guard<_ExtractKey, _Source>): New.
>>> (_Safe_unordered_container<>::_UMContMergeGuard<_ExtractKey,
>>> _Source>): New.
>>> (_Safe_unordered_container<>::_S_umc_guard<_ExtractKey, _Source>): New.
>>> (_Safe_unordered_container<>::_M_invalide_all): Make public.
>>> (_Safe_unordered_container<>::_M_invalide_if): Likewise.
>>> (_Safe_unordered_container<>::_M_invalide_local_if): Likewise.
>>> * include/debug/unordered_map
>>> (unordered_map<>::mapped_type, pointer, const_pointer):
>>> New typedef.
>>> (unordered_map<>::reference, const_reference,
>>> difference_type): New typedef.
>>> (unordered_map<>::get_allocator, empty, size, max_size):
>>> Add usings.
>>> (unordered_map<>::bucket_count, max_bucket_count, bucket):
>>> Add usings.
>>> (unordered_map<>::hash_function, key_equal, count,
>>> contains): Add usings.
>>> (unordered_map<>::operator[], at, rehash, reserve): Add
>>> usings.
>>> (unordered_map<>::merge): New.
>>> (unordered_multimap<>::mapped_type, pointer,
>>> const_pointer): New typedef.
>>> (unordered_multimap<>::reference, const_reference,
>>> difference_type): New typedef.
>>> (unordered_multimap<>::get_allocator, empty, size,
>>> max_size): Add usings.
>>> (unordered_multimap<>::bucket_count, max_bucket_count,
>>> bucket): Add usings.
>>> (unordered_multimap<>::hash_function, key_equal, count,
>>> contains): Add usings.
>>> (unordered_multimap<>::rehash, reserve): Add usings.
>>> (unordered_multimap<>::merge): New.
>>> * include/debug/unordered_set
>>> (unordered_set<>::mapped_type, pointer, const_pointer):
>>> New typedef.
>>> (unordered_set<>::reference, const_reference,
>>> difference_type): New typedef.
>>> (unordered_set<>::get_allocator, empty, size, max_size):
>>> Add usings.
>>> (unordered_set<>::bucket_count, max_bucket_count, bucket):
>>> Add usings.
>>> (unordered_set<>::hash_function, key_equal, count,
>>> contains): Add usings.
>>> (unordered_set<>::rehash, reserve): Add usings.
>>> (unordered_set<>::merge): New.
>>> (unordered_multiset<>::mapped_type, pointer,
>>> const_pointer): New typedef.
>>> (unordered_multiset<>::reference, const_reference,
>>> difference_type): New typedef.
>>> (unordered_multiset<>::get_allocator, empty, size,
>>> max_size): Add usings.
>>> (unordered_multiset<>::bucket_count, max_bucket_count,
>>> bucket): Add usings.
>>> (unordered_multiset<>::hash_function, key_equal, count,
>>> contains): Add usings.
>>> (unordered_multiset<>::rehash, reserve): Add usings.
>>> (unordered_multiset<>::merge): New.
>>> *
>>> testsuite/23_containers/unordered_map/debug/merge1_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_map/debug/merge2_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_map/debug/merge3_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_map/debug/merge4_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_set/debug/merge1_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_set/debug/merge2_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_set/debug/merge3_neg.cc: New test.
>>> *
>>> testsuite/23_containers/unordered_set/debug/merge4_neg.cc: New test.
>>> * testsuite/util/testsuite_abi.h: [_GLIBCXX_DEBUG] Use
>>> normal unordered container implementation.
>>>
>>> Tested under Linux x86_64.
>>>
>>> Ok to commit ?
>>>
>>> François
>>>
>>> On 25/10/21 8:08 pm, François Dumont wrote:
>>>> New patch with the proposed workaround below.
>>>>
>>>> I also slightly change the _M_merge_multi implementation so that if
>>>> the new hash code computation raise an exception the node is simply
>>>> not extracted rather than extracted and then released. This way, if
>>>> it takes place on the 1st moved node the _GLIBCXX_DEBUG mode won't
>>>> try to invalidate anything because the source size won't have changed.
>>>>
>>>> Ok to commit ?
>>>>
>>>> François
>>>>
>>>>
>>>> On 16/10/21 4:52 pm, Jonathan Wakely wrote:
>>>>>
>>>>> On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++,
>>>>> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@gcc.gnu.org>> wrote:
>>>>>
>>>>> Hi
>>>>>
>>>>> Here is the new proposal. My only concern is that we are
>>>>> also using
>>>>> hash or equal_to functors in the guard destructor.
>>>>>
>>>>>
>>>>>
>>>>> Can we catch any exception there, invalidate all iterators, and not
>>>>> rethrow the exception?
>>>>>
>>>>>
>>>>> I am going to enhance merge normal implementation to make
>>>>> use of
>>>>> the cached hash code when hash functors are the same between the
>>>>> source
>>>>> and destination of nodes. Maybe I'll be able to make use of it
>>>>> in Debug
>>>>> implementation too.
>>>>>
>>>>> François
>>>>>
>>>>>
>>>>> On 14/10/21 10:23 am, Jonathan Wakely wrote:
>>>>> > On Wed, 13 Oct 2021 at 18:10, François Dumont via Libstdc++
>>>>> > <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@gcc.gnu.org>> wrote:
>>>>> >> Hi
>>>>> >>
>>>>> >> libstdc++: [_GLIBCXX_DEBUG] Implement unordered
>>>>> container merge
>>>>> >>
>>>>> >> The _GLIBCXX_DEBUG unordered containers need a
>>>>> dedicated merge
>>>>> >> implementation
>>>>> >> so that any existing iterator on the transfered nodes
>>>>> is properly
>>>>> >> invalidated.
>>>>> >>
>>>>> >> Add typedef/using declaration for everything used as-is
>>>>> from normal
>>>>> >> implementation.
>>>>> >>
>>>>> >> libstdc++-v3/ChangeLog:
>>>>> >>
>>>>> >> * include/debug/safe_container.h
>>>>> (_Safe_container<>): Make
>>>>> >> all methods
>>>>> >> protected.
>>>>> >> * include/debug/safe_unordered_container.h
>>>>> >> (_Safe_unordered_container<>::_M_invalide_all): Make public.
>>>>> >> (_Safe_unordered_container<>::_M_invalide_if): Likewise.
>>>>> >> (_Safe_unordered_container<>::_M_invalide_local_if): Likewise.
>>>>> >> * include/debug/unordered_map
>>>>> >> (unordered_map<>::mapped_type, pointer, const_pointer): New
>>>>> >> typedef.
>>>>> >> (unordered_map<>::reference, const_reference,
>>>>> >> difference_type): New typedef.
>>>>> >> (unordered_map<>::get_allocator, empty, size, max_size):
>>>>> >> Add usings.
>>>>> >> (unordered_map<>::bucket_count, max_bucket_count, bucket):
>>>>> >> Add usings.
>>>>> >> (unordered_map<>::hash_function, key_equal, count,
>>>>> >> contains): Add usings.
>>>>> >> (unordered_map<>::operator[], at, rehash, reserve): Add usings.
>>>>> >> (unordered_map<>::merge): New.
>>>>> >> (unordered_multimap<>::mapped_type, pointer,
>>>>> >> const_pointer): New typedef.
>>>>> >> (unordered_multimap<>::reference, const_reference,
>>>>> >> difference_type): New typedef.
>>>>> >> (unordered_multimap<>::get_allocator, empty, size,
>>>>> >> max_size): Add usings.
>>>>> >> (unordered_multimap<>::bucket_count, max_bucket_count,
>>>>> >> bucket): Add usings.
>>>>> >> (unordered_multimap<>::hash_function, key_equal, count,
>>>>> >> contains): Add usings.
>>>>> >> (unordered_multimap<>::rehash, reserve): Add usings.
>>>>> >> (unordered_multimap<>::merge): New.
>>>>> >> * include/debug/unordered_set
>>>>> >> (unordered_set<>::mapped_type, pointer, const_pointer): New
>>>>> >> typedef.
>>>>> >> (unordered_set<>::reference, const_reference,
>>>>> >> difference_type): New typedef.
>>>>> >> (unordered_set<>::get_allocator, empty, size, max_size):
>>>>> >> Add usings.
>>>>> >> (unordered_set<>::bucket_count, max_bucket_count, bucket):
>>>>> >> Add usings.
>>>>> >> (unordered_set<>::hash_function, key_equal, count,
>>>>> >> contains): Add usings.
>>>>> >> (unordered_set<>::rehash, reserve): Add usings.
>>>>> >> (unordered_set<>::merge): New.
>>>>> >> (unordered_multiset<>::mapped_type, pointer,
>>>>> >> const_pointer): New typedef.
>>>>> >> (unordered_multiset<>::reference, const_reference,
>>>>> >> difference_type): New typedef.
>>>>> >> (unordered_multiset<>::get_allocator, empty, size,
>>>>> >> max_size): Add usings.
>>>>> >> (unordered_multiset<>::bucket_count, max_bucket_count,
>>>>> >> bucket): Add usings.
>>>>> >> (unordered_multiset<>::hash_function, key_equal, count,
>>>>> >> contains): Add usings.
>>>>> >> (unordered_multiset<>::rehash, reserve): Add usings.
>>>>> >> (unordered_multiset<>::merge): New.
>>>>> >> *
>>>>> >> testsuite/23_containers/unordered_map/debug/merge1_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >> testsuite/23_containers/unordered_map/debug/merge2_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >> testsuite/23_containers/unordered_map/debug/merge3_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >> testsuite/23_containers/unordered_map/debug/merge4_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >>
>>>>> testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >>
>>>>> testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >>
>>>>> testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >>
>>>>> testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >>
>>>>> testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >>
>>>>> testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >>
>>>>> testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >>
>>>>> testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >> testsuite/23_containers/unordered_set/debug/merge1_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >> testsuite/23_containers/unordered_set/debug/merge2_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >> testsuite/23_containers/unordered_set/debug/merge3_neg.cc:
>>>>> New test.
>>>>> >> *
>>>>> >> testsuite/23_containers/unordered_set/debug/merge4_neg.cc:
>>>>> New test.
>>>>> >> * testsuite/util/testsuite_abi.h:
>>>>> [_GLIBCXX_DEBUG] Use
>>>>> >> normal unordered container implementation.
>>>>> >>
>>>>> >> Tested under Linux x86_64.
>>>>> >>
>>>>> >> Ok to commit ?
>>>>> > Yes, thanks. But ...
>>>>> >
>>>>> > This looks like an improvement over what we have now, but not 100%
>>>>> > correct. The merge functions can exit via exception (if any hash
>>>>> > function or equality predicate throws), and if that happens
>>>>> the safe
>>>>> > iterators will not get invalidated. I think we need to call
>>>>> > _Base::merge in a try-block, and do the iterator invalidation
>>>>> whether
>>>>> > we return normally or via an exception.
>>>>> >
>>>>> > Something like:
>>>>> >
>>>>> > template<typename _H2, typename _P2>
>>>>> > void
>>>>> > merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
>>>>> > {
>>>>> > struct _Guard
>>>>> > {
>>>>> > _Guard(unordered_set& __source) noexcept
>>>>> > : _M_source(__source), _M_size(__source.size())
>>>>> > { }
>>>>> >
>>>>> > ~_Guard()
>>>>> > {
>>>>> > const size_type __size = _M_source.size();
>>>>> > if (__size != _M_size)
>>>>> > {
>>>>> > if (__size == 0)
>>>>> > _M_source._M_invalidate_all();
>>>>> > else
>>>>> > {
>>>>> > auto __pred = [&__source](auto __it)
>>>>> > { return
>>>>> __source.count(*__it) == 0; };
>>>>> > __source._M_invalidate_if(__pred);
>>>>> > __source._M_invalidate_local_if(__pred);
>>>>> > }
>>>>> > }
>>>>> > }
>>>>> >
>>>>> > _Guard(const _Guard&) = delete;
>>>>> >
>>>>> > unordered_set& _M_source;
>>>>> > const size_type _M_size;
>>>>> > };
>>>>> > _Guard __guard(__source);
>>>>> > _Base::merge(__source._M_base());
>>>>> > }
>>>>> >
>>>>>
>
More information about the Gcc-patches
mailing list