[Bug]: raw_hash_set: move assignment with unequal, non-propagating allocators uses the freed backing array

Describe the issue

When the allocators compare unequal and propagate_on_container_move_assignment is false (for example std::pmr::polymorphic_allocator with two different resources), move-assigning into a non-empty flat_hash_set/flat_hash_map leaves the destination in a broken state. An empty destination works. I expected the destination to end up with exactly the source's elements.

raw_hash_set::move_assign(that, std::false_type) destroys the destination with destructor_impl(), then re-inserts the source elements one by one. destructor_impl() frees the backing array but doesn't reset common(), so the inserts in move_elements_allocs_unequal() still see the old capacity and control pointer and probe freed memory. For the example below (16 elements on each side):

• ASan reports a heap-use-after-free in GroupSse2Impl::GroupSse2Impl() (hashtable_control_bytes.h:286), reached from insert() in move_elements_allocs_unequal() (raw_hash_set.h:3687). The memory was freed earlier in the same move_assign() call.
• With assertions enabled, (seq.index() <= capacity() && "full table!") && "Try enabling sanitizers." fails in find_or_prepare_insert_large() (raw_hash_set.h:3806).
• With NDEBUG, the assignment doesn't return within 20 seconds.

Smaller destinations are affected too. With 2, 3 or 8 elements, ASan again reports a heap-use-after-free, and builds without ASan abort with free(): double free detected in tcache 2. With a single element there is no heap backing array, so nothing is freed and nothing crashes, but the result is still wrong: dst.size() is 17 and the old key is still in the table.

It doesn't need a custom resource either. With std::pmr::monotonic_buffer_resource r1, r2; in the example below (it never frees, so there is nothing for ASan to report), the program prints dst.size()=32 in every build mode, and the 16 old keys can still be found in dst next to the 16 moved ones.

The existing NoPropagateOnMove.MoveAssignmentWithDifferentAlloc test moves into an empty table, where destructor_impl() has nothing to free, so it passes. The same test with a non-empty destination fails under ASan:

--- a/absl/container/internal/raw_hash_set_allocator_test.cc
+++ b/absl/container/internal/raw_hash_set_allocator_test.cc
@@ -439,6 +439,17 @@ TEST_F(NoPropagateOnMove, MoveAssignmentWithDifferentAlloc) {
   EXPECT_EQ(0, it->num_copies());
 }
 
+TEST_F(NoPropagateOnMove, MoveAssignmentWithDifferentAllocToNonEmptyTable) {
+  t1.insert(0);
+  Table u(0, a2);
+  for (int32_t i = 1; i <= 16; ++i) u.insert(i);
+  u = std::move(t1);
+  EXPECT_EQ(a2, u.get_allocator());
+  EXPECT_EQ(1, u.size());
+  EXPECT_NE(u.find(0), u.end());
+  EXPECT_EQ(u.find(1), u.end());
+}
+
 TEST_F(PropagateOnAll, Swap) {
   t1.insert(0);
   Table u(0, a2);

Suggested fix: reset common() after destructor_impl(), the same way assign_impl() and move_elements_allocs_unequal() already reset that.

--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -3709,6 +3709,8 @@ class raw_hash_set {
     // Aliasing can't happen here because allocs would compare equal above.
     assert(this != &that);
     destructor_impl();
+    // destructor_impl() leaves common() pointing at the freed backing array.
+    common() = CommonFields::CreateDefault<SooEnabled()>();
     // We can't take over that's memory so we need to move each element.
     // While moving elements, this should have that's hash/eq so copy hash/eq
     // before moving elements.

With both changes, the new test passes and the example below prints dst.size()=16 in ASan+UBSan, assert-enabled and NDEBUG builds. absl_raw_hash_set_allocator_test and absl_raw_hash_set_test also pass under ASan.

Steps to reproduce the problem

repro.cc:

#include <cstdio>
#include <memory_resource>
#include <new>

#include "absl/container/flat_hash_set.h"

// Forwards to operator new/delete so ASan sees the table's backing array.
// Two instances compare unequal.
struct NewDeleteResource : std::pmr::memory_resource {
  void* do_allocate(size_t n, size_t align) override {
    return ::operator new(n, std::align_val_t(align));
  }
  void do_deallocate(void* p, size_t, size_t align) override {
    ::operator delete(p, std::align_val_t(align));
  }
  bool do_is_equal(const memory_resource& o) const noexcept override {
    return this == &o;
  }
};

using Set = absl::flat_hash_set<int, absl::Hash<int>, std::equal_to<int>,
                                std::pmr::polymorphic_allocator<int>>;

int main() {
  NewDeleteResource r1, r2;
  Set dst{std::pmr::polymorphic_allocator<int>(&r1)};
  Set src{std::pmr::polymorphic_allocator<int>(&r2)};
  for (int i = 0; i < 16; ++i) dst.insert(i);
  for (int i = 100; i < 116; ++i) src.insert(i);

  dst = std::move(src);  // unequal allocators, no propagation on move

  std::printf("dst.size()=%zu\n", dst.size());
}

CMakeLists.txt, next to an abseil-cpp checkout:

cmake_minimum_required(VERSION 3.16)
project(repro CXX)
set(CMAKE_CXX_STANDARD 17)
add_subdirectory(abseil-cpp)
add_executable(repro repro.cc)
target_link_libraries(repro absl::flat_hash_set)

cmake -S . -B build-asan -DCMAKE_CXX_COMPILER=clang++ -DCMAKE_CXX_FLAGS=-fsanitize=address
cmake --build build-asan --target repro
./build-asan/repro

ASan output (abbreviated):

ERROR: AddressSanitizer: heap-use-after-free on address ...
READ of size 16 at ... thread T0
    #0 in absl::container_internal::GroupSse2Impl::GroupSse2Impl(absl::container_internal::ctrl_t const*)
    #1 in ...raw_hash_set<...>::find_or_prepare_insert_large<int>(int const&)

Without -fsanitize=address (default build type) it fails the assertion above. With -DCMAKE_BUILD_TYPE=Release it doesn't return (I stopped it after 20 seconds).

What version of Abseil are you using?

3a80a7794c7405b95dfa1f1afa26b37adf817636 (master)

What operating system and version are you using?

Ubuntu 22.04.5 LTS, x86_64 (kernel 6.8.0)

What compiler and version are you using?

Ubuntu clang version 15.0.7
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/lib/llvm-15/bin
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/12

What build system are you using?

cmake version 3.22.1

Additional context

Also reproduced with GCC 11.4: the ASan, assert-enabled and NDEBUG builds show the same three results as above.