Comments (5)
I can look into this first thing on Monday morning. Weekends are busy for me.
from unordered.
Thanks @cmazakas. I'll post details of what I could figure out with gdb
, in case it helps you save time.
Also, fyi the crash happens with SSE2 group15
as well, fwiw.
from unordered.
OK, I'll try to document what I saw while trying to triage this, in the hope that it helps...
Here's what happens in the crashing case:
-
When the map is initially filled with one or a few entries, the
table_core
'sarrays
member (thetable_array
) allocates both thegroups
and theelements
on the heap for the entries, as expected. Itsgroups_size_mask
is still just1
, just like it is for the default-constructed empty one, which is relevant later. -
For the default-constructed empty map, it has no allocated
elements
, and itsgroups
pointer is set to point to thestatic
"dummy" group. The dummy group is not initialized to all-zeroes, however; instead itsgroup15.m[]
values are initialized with some bits set. In the case of the plaingroup15
, them[0]
uint64_t
is set to0x0000000000004000ull
. (Is that bit set for the sentinel? I'm not clear on whatm[0]
orm[1]
represent exactly) -
When the map is copy-assigned from the empty one, inside
table_core::operator=(const table_core&)
, it does the following:- It invokes
clear()
, which (correctly) destroys the entries in the map and resetssize_ctrl.size
to0
. - During
clear()
, thegroup15.m[]
values are reset to purely0
, except the last group (the second group,groups[1]
, in this case) is set as a sentinel, which meansgroups[1].m[0]
has a bit set, whilegroups[1].m[1]
is just zero. - I should note that
clear()
never actually checks if the table is empty (ie,size_ctrl.size == 0
) when checking whether to destroy stuff, however, which will be important later. - After
clear()
, it then invokesnoshrink_reserve(0)
, which does nothing in this case. - Then it invokes
copy_elements_from()
, and since in this scenario thegroups_size_mask
of both the map and the empty one are the same, it will invokefast_copy_elements_from()
. And since the map has a non-nullelements
still, it will invokecopy_elements_array_from()
which will do nothing, and then it will also invokecopy_groups_array_from()
. Andcopy_groups_array_from()
willmemcpy
thegroups
from the empty one to this map. Which means the map will now have the samegroups
values of the dummy, since that's what the empty one used for itsgroups
. I'm not sure that is intentional? Because it now meansgroups[0].m[0]
will have the bit set too, not justgroups[1].m[0]
. - After all that it's done, so it never de-allocates the buffer pointed to by
elements
, which appears to be intentional. So it's left still pointing to the allocated buffer, which will be relevant later.
- It invokes
-
When the map is copy-assigned to the empty one again (or really it could be copy-assigned to a non-empty one here too and still crash), it does the following:
- Like in (3) above, it invokes
clear()
, but withinclear()
it doesn't check ifsize_ctrl.size == 0
first, and instead iterates through each group formatch_really_occupied()
. (it does this because theelements
pointer is not null) - Unfortunately
match_really_occupied()
will not return0
, and instead returns the value ofmatch_occupied()
. Which for the case of non-SSE plaingroup15
, will be the integer16384
. - Since it got
16384
,clear()
thinks there are entries to destroy, and thus tries to destroy already-free'd memory, and boom goes the dynamite.
- Like in (3) above, it invokes
The reason match_really_occupied()
returned the value of match_occupied()
instead of 0
is that the code for it is this:
static inline int match_really_occupied(group_type* pg,group_type* last)
{
/* excluding the sentinel */
return pg->match_occupied()&~(int(pg==last-1)<<(N-1));
}
The comment says it excludes the sentinel, but that will only happen if pg==last-1
. If pg
is NOT equal to last-1
, then that int(pg==last-1)
will be 0
, and thus int(pg==last-1)<<(N-1)
will be 0
, and thus ~()
of it will be all-ones, and thus it won't mask anything from pg->match_occupied()
.
And in this scenario, pg
is NOT equal to last-1
, when clear()
beings its iteration of the groups
in the map table. Because in the first iteration pg
will point to groups[0]
, while last-1
points to groups[1]
(last
is one past the end here).
So it won't mask the value it extracts from groups[0].m
, but that value is not 0
- it has a bit set, due to the memcpy
it did of the dummy group from the empty in the previous copy-assignment, as noted in (3.v) above.
What I'm not clear on is whether it's valid to have the sentinel bit set for groups[0].m
to begin with. If it is valid, then match_really_occupied()
is wrong. If it's not valid, then presumably the dummy's groups[0]
shouldn't have it set.
Also, I think clear()
should check for size_ctrl.size == 0
(ie, check empty()
) before iterating over all the groups. It's a waste of time/perf otherwise, imo.
For the non-crashing cases, there are different reasons they don't hit this bug:
-
If a move-assignment is used instead of the copy-assignment, it still invokes
clear()
, but in my particular use-case it will then invokereserve(0)
, which will actually end up de-allocating theelements
buffer altogether. Furthermore it will alsoswap()
the table arrays anyway. So the next time a copy-assignment or move-assignment happens,clear()
won't do anything becauseelements
will be null.- I should note that this only happens because
if(pocma||al()==x.al())
istrue
for my use-case. If it werefalse
instead, then I'm not sure if it would work correctly or not. (it looks like it will, becausecopy_elements_from()
is never invoked, but I haven't tested this)
- I should note that this only happens because
-
If the original map had more elements inserted in it, such that it had more groups, then it won't crash because the
groups_size_mask
values won't be the same for the map and the empty one. Socopy_elements_from()
won't invokefast_copy_elements_from()
, which means it won't invokecopy_groups_array_from()
and won'tmemcpy
the dummy groups from the empty one.
from unordered.
Hi @hadrielk, this is indeed a bug in table_core::fast_copy_elements_from
. Please try replacing this line:
with
if(arrays.elements&&x.arrays.elements){
from unordered.
@joaquintides yup that fixed it - thanks!
from unordered.
Related Issues (20)
- Is erase safe for unordered concurrent structures HOT 1
- boost::concurrent_flat_set missing capabilities HOT 1
- heap-user-after-free around foa::table_core::destroy_element HOT 7
- Much higher memory usage using Boost Interprocess HOT 4
- Change `is_avalanching` protocol to one based on `std::[true|false]_type` HOT 2
- Clang-12 CI issue, thrown `boost::interprocess::interprocess_exception`
- Error when emplacing in unordered_flat_map with std::atomic value HOT 2
- Using concurrent_flat_map with interprocess mapped memory allocator HOT 1
- Compilation error with MSVC 2022 HOT 3
- Use in-place construction for value for unordered_node_map::emplace() if the key+value size is large? HOT 1
- Element locking in `boost::concurrent_flat_set::*visit` operations HOT 1
- Won't compile with c++ modules using clang
- Requirements on keys for bulk visitation are overly restrictive
- Incorrect use of undefined Boost.Config macro `BOOST_MSVC` in Natvis test file
- std::forward is called twice for the parameter HOT 1
- [FR] Add extract-like functionality to concurrent containers HOT 3
- Missing assignment operator=(std::initializer_list<value_type>) HOT 1
- Unification of internal `node_type`s HOT 1
- [FR] unordered flat multimap HOT 1
- Keeping bloat under control HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from unordered.