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++, > >>> <libstd...@gcc.gnu.org <mailto:libstdc%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++ > >>> > <libstd...@gcc.gnu.org <mailto:libstdc%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()); > >>> > } > >>> > > >>> > >> > > > -- H.J.
