[Bug]: linked_hash_set/map: move assignment with unequal, non-propagating allocators uses freed list nodes (set), fails to compile (map)

[Fengxiaoxx]

Describe the issue

absl::linked_hash_set stores its elements in a std::list and indexes them
with a flat_hash_set of std::list iterators. Its move assignment operator
takes over that index verbatim:

set_ = std::move(other.set_);
list_ = std::move(other.list_);
other.set_.clear();
other.list_.clear();

When the allocator does not propagate on move assignment and the two
allocators compare unequal (for example two
std::pmr::polymorphic_allocators that use different memory_resources),
std::list cannot take over the source's nodes: it re-creates them with the
destination's allocator. The index taken over from other.set_ still holds
iterators into the source's old nodes, and other.list_.clear() then frees
those nodes. The first keyed operation (find, contains, erase, ...)
dereferences a dangling iterator.

With AddressSanitizer this is a heap-use-after-free READ in
Wrapped::operator() (linked_hash_set.h:98); without a sanitizer the first
keyed operation reads freed memory and typically crashes with SIGSEGV. When
the allocators compare equal the list takes over the nodes and there is no
problem.

absl::linked_hash_map uses the same pattern and has a related problem in
the same configuration: it does not compile, because with a non-propagating
allocator std::list's move assignment element-assigns, which is ill-formed
for std::pair<const K, V> (both libstdc++ and libc++ reject it).

Steps to reproduce the problem

// absl::linked_hash_set keeps std::list iterators as the keys of its internal
// flat_hash_set.  With a non-propagating allocator that is unequal between the
// two sets, std::list move-assignment re-creates the list nodes instead of
// stealing them, while `set_ = std::move(other.set_)` still copies the
// iterators verbatim (linked_hash_set.h:257-265); `other.list_.clear()` then
// frees the original nodes and every lookup dereferences a dangling iterator
// inside Wrapped::operator() (linked_hash_set.h:98).
//
// std::pmr::polymorphic_allocator has propagate_on_container_move_assignment ==
// false and is_always_equal == false, so the configuration is standard.
//
// Usage: ./poc [control|trigger]
//   control - equal allocators: std::list steals the nodes, keys stay valid.
//   trigger - unequal allocators: erase() reads the freed std::list nodes.

#include <cstddef>
#include <cstdio>
#include <cstring>
#include <functional>
#include <memory_resource>
#include <type_traits>
#include <utility>

#include "absl/container/linked_hash_set.h"
#include "absl/hash/hash.h"

static_assert(
    !std::allocator_traits<std::pmr::polymorphic_allocator<int>>::
        propagate_on_container_move_assignment::value,
    "POCMA must be false");
static_assert(
    !std::allocator_traits<std::pmr::polymorphic_allocator<int>>::
        is_always_equal::value,
    "is_always_equal must be false");

// Forwards straight to ::operator new/delete so AddressSanitizer observes
// every allocation/free of the std::list nodes.
struct Res : std::pmr::memory_resource {
  void* do_allocate(std::size_t bytes, std::size_t align) override {
    return ::operator new(bytes, std::align_val_t(align));
  }
  void do_deallocate(void* p, std::size_t bytes, std::size_t align) override {
    ::operator delete(p, std::align_val_t(align));
  }
  bool do_is_equal(const std::pmr::memory_resource& o) const noexcept override {
    return this == &o;
  }
};

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

static void Demo(bool unequal) {
  Res r1, r2;
  Set a{Alloc(&r1)};
  Set b{Alloc(unequal ? &r2 : &r1)};
  a.insert(11);
  a.insert(22);
  a.insert(33);
  std::printf("  [%s] a.size=%zu b.size=%zu\n", unequal ? "unequal" : "equal",
              a.size(), b.size());
  std::fflush(stdout);

  b = std::move(a);  // linked_hash_set::operator=(linked_hash_set&&)

  std::printf("  [%s] after move-assign: b.size=%zu\n",
              unequal ? "unequal" : "equal", b.size());
  std::fflush(stdout);

  // Every keyed API now probes the iterator keys stored in set_.
  const std::size_t erased = b.erase(22);
  std::printf("  [%s] erase(22)=%zu b.size=%zu\n", unequal ? "unequal" : "equal",
              erased, b.size());
  std::fflush(stdout);
}

int main(int argc, char** argv) {
  const bool trigger = !(argc > 1 && std::strcmp(argv[1], "control") == 0);
  if (trigger) {
    std::printf("[trigger] unequal allocators: list nodes re-created, keys dangle\n");
    std::fflush(stdout);
    Demo(true);
    std::printf("[trigger] survived\n");
  } else {
    std::printf("[control] equal allocators: list steals the nodes, keys valid\n");
    std::fflush(stdout);
    Demo(false);
    std::printf("[control] survived\n");
  }
  return 0;
}

$ clang++ -g -O1 -DNDEBUG -std=c++17 -fsanitize=address -I abseil-cpp \
    poc_set.cc <libabsl_*.a> -lpthread -o poc
$ ./poc trigger

(the report below was produced with -fdebug-prefix-map so that the paths in
it are relative)

[trigger] unequal allocators: list nodes re-created, keys dangle
  [unequal] a.size=3 b.size=0
  [unequal] after move-assign: b.size=3
=================================================================
==9768==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000080 at pc 0x644264fb31c8 bp 0x7ffcbcf9d600 sp 0x7ffcbcf9d5f8
READ of size 4 at 0x603000000080 thread T0
    #0 0x644264fb31c7 in std::equal_to<int>::operator()(int const&, int const&) const /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_function.h:370:16
    #1 0x644264fb31c7 in decltype(this->fn_(ToKey(fp)...)) absl::linked_hash_set<int, absl::hash_internal::Hash<int>, std::equal_to<int>, std::pmr::polymorphic_allocator<int> >::Wrapped<std::equal_to<int> >::operator()<std::_List_iterator<int> const&, int const&>(std::_List_iterator<int> const&, int const&) const abseil-cpp/absl/container/linked_hash_set.h:98:14
[... elided]
    #9 0x644264faee8b in unsigned long absl::linked_hash_set<int, absl::hash_internal::Hash<int>, std::equal_to<int>, std::pmr::polymorphic_allocator<int> >::erase<int>(int const&) abseil-cpp/absl/container/linked_hash_set.h:317:23
    #10 0x644264fae41b in Demo(bool) ./poc_set.cc:72:32
    #11 0x644264fad930 in main ./poc_set.cc
[... elided]
0x603000000080 is located 16 bytes inside of 24-byte region [0x603000000070,0x603000000088)
freed by thread T0 here:
[... elided]
    #1 0x644264faf3bb in Res::do_deallocate(void*, unsigned long, unsigned long) ./poc_set.cc:43:5
[... elided]
SUMMARY: AddressSanitizer: heap-use-after-free /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_function.h:370:16 in std::equal_to<int>::operator()(int const&, int const&) const

For the map, poc_map.cc is the same program with linked_hash_map in place
of linked_hash_set. Its key lines are:

#include "absl/container/linked_hash_map.h"
using Pair = std::pair<const int, int>;
using Alloc = std::pmr::polymorphic_allocator<Pair>;
using Map =
    absl::linked_hash_map<int, int, absl::Hash<int>, std::equal_to<int>, Alloc>;
  Map a{Alloc(&r1)};
  Map b{Alloc(unequal ? &r2 : &r1)};
  a.insert({11, 110});
  a.insert({22, 220});
  a.insert({33, 330});
  b = std::move(a);  // linked_hash_map::operator=(linked_hash_map&&)

It does not compile (same command as above, with poc_map.cc):

In file included from poc_map.cc:24:
In file included from abseil-cpp/absl/container/linked_hash_map.h:38:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/list:64:
/usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/list.tcc:316:21: error: object of type 'std::pair<const int, int>' cannot be assigned because its copy assignment operator is implicitly deleted
          *__first1 = *__first2;
                    ^
[... elided]
1 error generated.

What version of Abseil are you using?

08e7a252 (master of 2026-09-23; includes the #2168 fix 7f6e4974).

What operating system and version are you using?

Ubuntu 22.04.

What compiler and version are you using?

clang 14.0.0 with libstdc++ 11, and clang 22.0.0git with libc++ 22; C++17.

What build system are you using?

CMake 3.22 with Ninja for the library; the reproducer was compiled directly
against the static libraries.

Additional context

The same allocator configuration was reported for raw_hash_set in #2168
and fixed by 7f6e4974. That fix does not cover this issue: here the index
holds std::list iterators, and the list's move assignment invalidates them
because it cannot take over the source's nodes. The reproducer above still
fails on 08e7a252, which contains 7f6e4974.