[PATH][_GLIBCXX_DEBUG] Fix unordered container merge
François Dumont
frs.dumont@gmail.com
Mon Nov 8 21:36:10 GMT 2021
Yet another version this time with only 1 guard implementation. The
predicate to invalidate the safe iterators has been externalized.
Ok to commit ?
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());
>>> > }
>>> >
>>>
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: merge.patch
Type: text/x-patch
Size: 34367 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20211108/d078d5c3/attachment-0001.bin>
More information about the Gcc-patches
mailing list