public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
From: "François Dumont" <frs.dumont@gmail.com>
To: "H.J. Lu" <hjl.tools@gmail.com>
Cc: Jonathan Wakely <jwakely.gcc@gmail.com>,
	Jonathan Wakely <jwakely@redhat.com>,
	libstdc++ <libstdc++@gcc.gnu.org>,
	gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge
Date: Wed, 10 Nov 2021 06:44:55 +0100	[thread overview]
Message-ID: <7043bd08-3035-dc76-bed2-c7911d6dab59@gmail.com> (raw)
In-Reply-To: <CAMe9rOoA-jREgx9mnvb1_UWzBMLKkFW4onFFovCer5QsQYbgWg@mail.gmail.com>

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


  reply	other threads:[~2021-11-10  5:45 UTC|newest]

Thread overview: 21+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-10-13 17:10 François Dumont
2021-10-14  8:23 ` Jonathan Wakely
2021-10-16 13:47   ` François Dumont
2021-10-16 14:52     ` Jonathan Wakely
2021-10-21 16:51       ` François Dumont
2021-10-21 16:55         ` Jonathan Wakely
2021-10-22  5:22           ` François Dumont
2021-10-25 18:08       ` François Dumont
2021-11-06 13:51         ` François Dumont
2021-11-08 21:36           ` François Dumont
2021-11-09 16:25             ` Jonathan Wakely
2021-11-10  5:47               ` François Dumont
2021-11-10  9:38                 ` Jonathan Wakely
2021-11-15 18:16                   ` François Dumont
2021-11-10 11:55               ` Jonathan Wakely
2021-11-11 20:41                 ` Jonathan Wakely
2021-11-11 21:33                   ` François Dumont
2021-11-11 22:01                     ` Jonathan Wakely
2021-11-10  0:05             ` H.J. Lu
2021-11-10  5:44               ` François Dumont [this message]
2021-11-10  7:26                 ` Jonathan Wakely

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=7043bd08-3035-dc76-bed2-c7911d6dab59@gmail.com \
    --to=frs.dumont@gmail.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=hjl.tools@gmail.com \
    --cc=jwakely.gcc@gmail.com \
    --cc=jwakely@redhat.com \
    --cc=libstdc++@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).