Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge

["H.J. Lu" <hjl.tools@gmail.com>]

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());
> >>>     >      }
> >>>     >
> >>>
> >>
> >
>


-- 
H.J.