From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52e.google.com (mail-ed1-x52e.google.com [IPv6:2a00:1450:4864:20::52e]) by sourceware.org (Postfix) with ESMTPS id 803AD385842B; Wed, 10 Nov 2021 05:45:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 803AD385842B Received: by mail-ed1-x52e.google.com with SMTP id r12so5858843edt.6; Tue, 09 Nov 2021 21:45:03 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=brciMUj7LSBiZZEaolzXYZXcVXw26lL204Z9C0jtcTw=; b=J1J9Pv6uNqQ4zaVT7a9vL80zb7G+vXg2Y/G1w9IjbkOELe0wzz6lZ9sxvMGvMlSzjO cRe92kJEgH0mkw29CVgAnUx926M9X87Ud7l4cZwddmwwrsd3jGmhhaN3zZcLDg7OryqW gq/S+VjSRCXSItnCNkGS4R8x3yBED3+dDrN81B9we2krT8Na1Ud9MsVLo6c4c9WPW3wX w7eG8/NLc3kf14P3EKetNNgEYgsXUVweWuGXvS/kpFROk4eW/XDc7z4JZDSnn2bCCQ+l 48+u5w2tQq5l9Ht8MuSIiRpYmse+sKERY15OvLfPDis1DQVgF9xU8rAHUJAThvRmST+Y ZPuw== X-Gm-Message-State: AOAM5315tFCKfhI+59Aws+XhcVsVzNfARiXbwrJGq+avCuhGXmFyOiwr ydiehkBChF04IBrhiQsGxZO8FEA359k= X-Google-Smtp-Source: ABdhPJxpfQy97p4OC4OzAZiuKauLmaUlEWBjwwhYPr6VyvkjN70QsmYbGvG3jHOvSsdaT1ucEYf/7Q== X-Received: by 2002:a17:906:a10c:: with SMTP id t12mr16922536ejy.429.1636523098965; Tue, 09 Nov 2021 21:44:58 -0800 (PST) Received: from [10.24.4.78] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id t22sm11956591eds.65.2021.11.09.21.44.57 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 09 Nov 2021 21:44:58 -0800 (PST) Subject: Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge To: "H.J. Lu" Cc: Jonathan Wakely , Jonathan Wakely , libstdc++ , gcc-patches 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> From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Message-ID: <7043bd08-3035-dc76-bed2-c7911d6dab59@gmail.com> Date: Wed, 10 Nov 2021 06:44:55 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: fr X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, KAM_SHORT, NICE_REPLY_A, RCVD_IN_ABUSEAT, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=no 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 05:45:06 -0000 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 > 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 Allocator>::value_type* hash_table Allocator>::alloc_entries(size_t) const [with Descriptor = > hash_map >::hash_entry; bool Lazy = > false; Allocator = xcallocator]’, > inlined from ‘void hash_table Allocator>::expand() [with Descriptor = hash_map auto_vec >::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::expand() [with > Descriptor = hash_map >::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::expand() [with Descriptor = > hash_map >::hash_entry; bool Lazy = > false; Allocator = xcallocator]’: > ../../src-master/gcc/hash-table.h:779:1: note: ‘void > hash_table::expand() [with Descriptor = > hash_map >::hash_entry; bool Lazy = > false; Allocator = xcallocator]’ was declared here > 779 | hash_table::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++, >>>>> > 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++ >>>>> > > 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 >>>>> > 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()); >>>>> > } >>>>> > >>>>> >