Copy-assignment from a default-constructed unordered_flat_map can double-free?

[hadrielk]

Copy-assignment from a default-constructed unordered_flat_map can double-free?

[cmazakas]

I can look into this first thing on Monday morning. Weekends are busy for me.

[hadrielk]

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.

[hadrielk]

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:

1. When the map is initially filled with one or a few entries, the table_core's arrays member (the table_array) allocates both the groups and the elements on the heap for the entries, as expected. Its groups_size_mask is still just 1, just like it is for the default-constructed empty one, which is relevant later.

2. For the default-constructed empty map, it has no allocated elements, and its groups pointer is set to point to the static "dummy" group. The dummy group is not initialized to all-zeroes, however; instead its group15.m[] values are initialized with some bits set. In the case of the plain group15, the m[0] uint64_t is set to 0x0000000000004000ull. (Is that bit set for the sentinel? I'm not clear on what m[0] or m[1] represent exactly)

3. When the map is copy-assigned from the empty one, inside table_core::operator=(const table_core&), it does the following:

   1. It invokes clear(), which (correctly) destroys the entries in the map and resets size_ctrl.size to 0.
   2. During clear(), the group15.m[] values are reset to purely 0, except the last group (the second group, groups[1], in this case) is set as a sentinel, which means groups[1].m[0] has a bit set, while groups[1].m[1] is just zero.
   3. 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.
   4. After clear(), it then invokes noshrink_reserve(0), which does nothing in this case.
   5. Then it invokes copy_elements_from(), and since in this scenario the groups_size_mask of both the map and the empty one are the same, it will invoke fast_copy_elements_from(). And since the map has a non-null elements still, it will invoke copy_elements_array_from() which will do nothing, and then it will also invoke copy_groups_array_from(). And copy_groups_array_from() will memcpy the groups from the empty one to this map. Which means the map will now have the same groups values of the dummy, since that's what the empty one used for its groups. I'm not sure that is intentional? Because it now means groups[0].m[0] will have the bit set too, not just groups[1].m[0].
   6. 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.

4. 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:

   1. Like in (3) above, it invokes clear(), but within clear() it doesn't check if size_ctrl.size == 0 first, and instead iterates through each group for match_really_occupied(). (it does this because the elements pointer is not null)
   2. Unfortunately match_really_occupied() will not return 0, and instead returns the value of match_occupied(). Which for the case of non-SSE plain group15, will be the integer 16384.
   3. 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.

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:

1. If a move-assignment is used instead of the copy-assignment, it still invokes clear(), but in my particular use-case it will then invoke reserve(0), which will actually end up de-allocating the elements buffer altogether. Furthermore it will also swap() the table arrays anyway. So the next time a copy-assignment or move-assignment happens, clear() won't do anything because elements will be null.

   • I should note that this only happens because if(pocma||al()==x.al()) is true for my use-case. If it were false instead, then I'm not sure if it would work correctly or not. (it looks like it will, because copy_elements_from() is never invoked, but I haven't tested this)

2. 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. So copy_elements_from() won't invoke fast_copy_elements_from(), which means it won't invoke copy_groups_array_from() and won't memcpy the dummy groups from the empty one.

[joaquintides]

Hi @hadrielk, this is indeed a bug in table_core::fast_copy_elements_from. Please try replacing this line:

unordered/include/boost/unordered/detail/foa/core.hpp

Line 1873 in 5339bf6

if(arrays.elements){

with

    if(arrays.elements&&x.arrays.elements){

[hadrielk]

@joaquintides yup that fixed it - thanks!