From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pl1-x630.google.com (mail-pl1-x630.google.com [IPv6:2607:f8b0:4864:20::630]) by sourceware.org (Postfix) with ESMTPS id EA0223858405; Wed, 10 Nov 2021 00:05:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EA0223858405 Received: by mail-pl1-x630.google.com with SMTP id b11so1439259pld.12; Tue, 09 Nov 2021 16:05:47 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=XeTNpkOjm7beuElzCHd8colQ0kem3Qb8tR8re5H2ryQ=; b=3s0CVdpfcFHLNiFLPZU7skGNqvIGM9F0p+wWhKYFSrNJxyDxuvwNldxg9Ll/VX0hga 0Bctj45iUBQBVGn4LUaN3XE6j3EqBcKRGPu4r2WGGDIv5C94qNOTSFqUuvg94AgFbw/n 1XMYeImvTpX0Qfp48txoAmubQ2IXUuylmGrOQoeeyxezlK64cioGj5bi7s2ZZ4jJ7aKG srUCtG6S/2u+6E9tnyGxmMIn8KVjTp7jqkmGzPdFEqD/uaCZPSlCWyGvmweWbYTV6mY1 pZfJOlGjvn8RoWNYFLxxz96m6jeXDQIRMeTzqRMhgprwD/qhcD+rNHFe864IeTPIzJ+1 cFBA== X-Gm-Message-State: AOAM532w8+EAEi4HdiPj+VGbu5f0DQ6jbRguOaN7EgkUtzeark9Xo76N T0Bv291SssfosWvrf/mt9H01/W903oll1Qh3ZKM= X-Google-Smtp-Source: ABdhPJyCjRfanAvxEcEIaOGY8l/HqZp5DUH/idTdptCR/yIVUAlr8AiOS5xq5lmBEVMivtTKVd+R2aDxUy959q6X0dA= X-Received: by 2002:a17:90b:3b82:: with SMTP id pc2mr11958924pjb.120.1636502746809; Tue, 09 Nov 2021 16:05:46 -0800 (PST) MIME-Version: 1.0 References: <4eec3fb9-851e-3e4e-f9f4-1110db3af747@gmail.com> <6c349652-8b6f-2027-08c3-6ce58a765aeb@gmail.com> <22bf1b42-8cf4-7a6e-d5dc-c322ccbb2b46@gmail.com> <68641ea0-2a14-e3a5-8315-a7b3a9c1fdb4@gmail.com> In-Reply-To: From: "H.J. Lu" Date: Tue, 9 Nov 2021 16:05:10 -0800 Message-ID: Subject: Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge To: =?UTF-8?Q?Fran=C3=A7ois_Dumont?= Cc: Jonathan Wakely , Jonathan Wakely , "libstdc++" , gcc-patches Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-3023.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 10 Nov 2021 00:05:51 -0000 On Mon, Nov 8, 2021 at 1:37 PM Fran=C3=A7ois Dumont via Gcc-patches 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 =E2=80=98hash_table::value_type* hash_table::alloc_entries(size_t) const [with Descriptor =3D hash_map >::hash_entry; bool Lazy =3D false; Allocator =3D xcallocator]=E2=80=99, inlined from =E2=80=98void hash_table::expand() [with Descriptor =3D hash_map >::hash_entry; bool Lazy =3D false; Allocator =3D xcallocator]=E2=80=99 at ../../src-master/gcc/hash-table.h:802:40: ../../src-master/gcc/system.h:784:34: error: section type conflict with =E2=80=98void hash_table::expand() [with Descriptor =3D hash_map >::hash_entry; bool Lazy =3D false; Allocator =3D xcallocator]=E2=80=99 784 | ((void)(!(EXPR) ? fancy_abort (__FILE__, __LINE__, __FUNCTION__), 0 : 0)) | ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ../../src-master/gcc/hash-table.h:715:3: note: in expansion of macro =E2=80=98gcc_assert=E2=80=99 715 | gcc_assert (nentries !=3D 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 =E2=80=98void hash_table::expand() [with Descriptor =3D hash_map >::hash_entry; bool Lazy =3D false; Allocator =3D xcallocator]=E2=80=99: ../../src-master/gcc/hash-table.h:779:1: note: =E2=80=98void hash_table::expand() [with Descriptor =3D hash_map >::hash_entry; bool Lazy =3D false; Allocator =3D xcallocator]=E2=80=99 was declared here 779 | hash_table::expand () | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > On 06/11/21 2:51 pm, Fran=C3=A7ois 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 tes= t. > > * > > testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc: New tes= t. > > * > > testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc: New tes= t. > > * > > testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc: New tes= t. > > * > > testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc: New tes= t. > > * > > testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc: New tes= t. > > * > > testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc: New tes= t. > > * > > testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc: New tes= t. > > * > > 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=C3=A7ois > > > > On 25/10/21 8:08 pm, Fran=C3=A7ois 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=C3=A7ois > >> > >> > >> On 16/10/21 4:52 pm, Jonathan Wakely wrote: > >>> > >>> > >>> On Sat, 16 Oct 2021, 14:49 Fran=C3=A7ois Dumont via Libstdc++, > >>> > 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=C3=A7ois > >>> > >>> > >>> On 14/10/21 10:23 am, Jonathan Wakely wrote: > >>> > On Wed, 13 Oct 2021 at 18:10, Fran=C3=A7ois Dumont via Libstdc+= + > >>> > > wrot= e: > >>> >> 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 using= s. > >>> >> (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 1= 00% > >>> > correct. The merge functions can exit via exception (if any has= h > >>> > 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 > >>> > 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 =3D _M_source.size(); > >>> > if (__size !=3D _M_size) > >>> > { > >>> > if (__size =3D=3D 0) > >>> > _M_source._M_invalidate_all(); > >>> > else > >>> > { > >>> > auto __pred =3D [&__source](auto __it) > >>> > { return > >>> __source.count(*__it) =3D=3D 0; }; > >>> > __source._M_invalidate_if(__pred); > >>> > __source._M_invalidate_local_if(__pred); > >>> > } > >>> > } > >>> > } > >>> > > >>> > _Guard(const _Guard&) =3D delete; > >>> > > >>> > unordered_set& _M_source; > >>> > const size_type _M_size; > >>> > }; > >>> > _Guard __guard(__source); > >>> > _Base::merge(__source._M_base()); > >>> > } > >>> > > >>> > >> > > > --=20 H.J.